试一下迭代版的归并排序，它比所有的排序算法都要慢，我错在哪里？
public static void quickSort(int[] arr) {
int size = arr.length;
int count = 0;
int[] stackArr = new int[size];
stackArr[count] = 0;
stackArr[++count] = size - 1;
while (count >= 0) {
int end = stackArr[count--];
int start = stackArr[count--];
int pivot = partition(arr, start, end);
if (pivot - 1 > start) {
stackArr[++count] = start;
stackArr[++count] = pivot - 1;
}
if (pivot + 1 < end) {
stackArr[++count] = pivot + 1;
stackArr[++count] = end;
}
}
}
public static int partition(int[] arr, int start, int end) {
int countIndex = start ;
for (int i = start; i < end; i++) {
if (arr[i] <= arr[end]) {
swap(arr, i, countIndex);
countIndex++;
}
}
swap(arr, countIndex, end);
return countIndex;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}我刚试着用java写了一个quickSort（）方法来测试，它的执行速度真的很慢。我想知道是什么问题？
1条答案
按热度按时间ztigrdn81#
问题中的代码使用最后一个元素作为pivot，这是已经排序或反向排序的数据的最坏情况。问题中没有显示对排序函数进行基准测试的代码：第一个排序器可能会对数组进行排序，然后将排序后的数组用于基准中的其余排序函数。为了避免这种情况，请使用第二个数组。在创建随机化数组之后，对于每个排序测试，请将其复制到第二个数组并在第二个数组上测试排序。
问题还在于使用了Lomuto分区方案，如果存在重复值，则会向最差情况降级。
下面的代码几乎是Hoare在没有本机堆栈的系统上实现的快速排序的原始版本的副本。为了将堆栈大小限制为O（log2（n）），较大的分区索引被推送到堆栈上，而较小的分区通过循环回分区代码来处理。