我的快速排序算法对于较大的 n 值失败，并且仅当数组不是随机的。我尝试过在各种数组上使用该算法。当我使用随机数字数组（对于n的任何值）时，它可以正常工作，但是对于包含相同值或按升序或降序排列的值的数组，它失败了。这也只有在n大约是abov 6000时。（当n为<5000时，它可以完美地工作）
我已经尝试过使用不同版本的快速排序。一个使用while循环而不是递归，并且它工作得很好。就像我说过的，只有当n对于非随机化数组大于6000时，我的算法才会失败，对于5000或更低，它的效果很好。
void quicksort(int a[], int low, int high) {
if (low < high) {
int index = partition(a, low, high); // error
quicksort(a, low, index - 1); // error
quicksort(a, index + 1, high);
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
//int j = low;
for (int j = low; j < high; j++) {
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
上面我有我的快速排序算法。对于 n>6000（以及数组不是随机的）而失败的那个。
下面是适用于 n 的所有值和任何类型的数组的代码。
public void quicksort(int[] data, int low, int high)
{ // 1 or 0 items are sorted by default
if(high - low < 1)
return;
int left = low;
int right = high;
int pivot = data[low + (high - low) / 2];
while(left <= right)
{ // Increment left pointer until left >= pivot
while(data[left] < pivot)
left++;
// Increment right pointer until right <= pivot
while(data[right] > pivot)
right--;
// If left < right; swap values
if(left <= right)
{ int temp = data[left];
data[left] = data[right];
data[right] = temp;
left++;
right--;
}
}
// quick_sort 'lesser values'
quicksort(data, low, right);
// quick_sort 'greater values'
quicksort(data, left, high);
}
终端专门在两行中显示错误。（我在第一个快速排序方法中标记为错误的行）。
互换的青春
相关分类