我有一个简单的方法来使用快速排序对 int 数组进行排序。我不知道如何正确计算交换和比较的次数,因为该算法是递归的:
public void quicksort(int tablica[], int x, int y) {
int i,j,v,temp;
i=x;
j=y;
int swaps=0;
int comparisons=0;
v=tablica[(x+y) / 2];
while (i<=j)
{
while (tablica [i] <v)
{
i++;
}
while (tablica [j] >v)
{
j--;
}
if (i<=j){
temp = tablica [i];
tablica [i]=tablica[j];
tablica [j] = temp;
i++;
j--;
swaps++;
}
comparisons++;
}
if (x<j)
quicksort(tablica,x,j);
if (i<y)
quicksort(tablica,i,y);
System.out.println("Comparisons: " + comparisons);
System.out.println("Swaps: " + swaps);
}
使用小(10 个整数)数组运行它会返回:
Comparisons: 1
Swaps: 1
Comparisons: 1
Swaps: 1
Comparisons: 2
Swaps: 2
Comparisons: 1
Swaps: 1
Comparisons: 1
Swaps: 1
Comparisons: 1
Swaps: 1
Comparisons: 2
Swaps: 1
Comparisons: 4
Swaps: 4
如何正确地做到这一点?
最佳答案
定义一个类变量,并在每次运行快速排序方法时更新类变量。
示例
public class example {
private int swaps=0;
private int comparisons=0;
public void quicksort(int tablica[], int x, int y) {
int i,j,v,temp;
i=x;
j=y;
v=tablica[(x+y) / 2];
while (i<=j)
{
while (tablica [i] <v)
{
i++;
}
while (tablica [j] >v)
{
j--;
}
if (i<=j){
temp = tablica [i];
tablica [i]=tablica[j];
tablica [j] = temp;
i++;
j--;
swaps++;
}
comparisons++;
}
if (x<j)
quicksort(tablica,x,j);
if (i<y)
quicksort(tablica,i,y);
System.out.println("Comparisons: " + comparisons);
System.out.println("Swaps: " + swaps);
}
}
关于java - 如何在Java中的快速排序中计算比较和交换?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43357069/