gpt4 book ai didi

c++ - 如果有重复值,快速排序无限循环

转载 作者:太空狗 更新时间:2023-10-29 20:26:17 25 4
gpt4 key购买 nike

我有一个快速排序程序,在我尝试对具有重复数字的数组进行排序之前效果很好。程序陷入无限循环。我相信这发生在 While(lower < upper)代码块。

void quickSort(int array[], int size){
if(size < 2) return;

int pivot, lower, upper, temp;

//Set the indeces for the first and last elements
lower = 0;
upper = size - 1;

//Select pivot element randomly
pivot = array[rand() % (size)];

while(lower < upper){
//Lower must be a number < than pivot and upper a number >= pivot
while(array[lower] < pivot){
lower++;
}
while(array[upper] > pivot){
upper--;
}

//Swap upper and lower
temp = array[lower];
array[lower] = array[upper];
array[upper] = temp;
}

//Repeat the past actions on the two partitions of the array recursively
quickSort(array, lower);
quickSort(&array[lower+1], size-lower-1);
}

最佳答案

编辑:添加代码。

来自 Wikipedia ,就地快速排序的伪代码如下:
(不是说要盲目信任)

function quicksort(array)
if length(array) > 1
pivot := select any element of array
left := first index of array
right := last index of array
while left ≤ right
while array[left] < pivot
left := left + 1
while array[right] > pivot
right := right - 1
if left ≤ right
swap array[left] with array[right]
left := left + 1
right := right - 1
quicksort(array from first index to right)
quicksort(array from left to last index)

因此您看到它与您的算法非常相似,只是稍作修改。

while(lower <= upper){

此外,只有在 lower <= upper 时才需要交换然后更新索引。

并且您的代码在递归调用方面有所不同:

quicksort(array from first index to right) {array[0] to array[upper]}
quicksort(array from left to last index) {array[lower] to array[size-1]}

这是因为现在它已经退出 while 循环,upper 小于 lower。

完整的工作代码:

#include <iostream>
#include <cstdlib>
using namespace std;

void quickSort(int array[], int size){
if(size < 2) return;

int pivot, lower, upper, temp;

//Set the indeces for the first and last elements
lower = 0;
upper = size - 1;

//Select pivot element randomly
pivot = array[rand() % (size)];

while(lower <= upper){
//Lower must be a number < than pivot and upper a number >= pivot
while(array[lower] < pivot){
lower++;
}
while(array[upper] > pivot){
upper--;
}

//Swap upper and lower
if ( lower <= upper ) {
temp = array[lower];
array[lower] = array[upper];
array[upper] = temp;
lower++;
upper--;
}
}

//Repeat the past actions on the two partitions of the array recursively
quickSort(array, upper+1);
quickSort(&array[lower], size-lower);
}

int main() {
// your code goes here
int myArray[] = { 10, 9, 8, 7, 7, 7, 7, 3, 2, 1};
quickSort( myArray, 10 );
for ( int i = 0; i < 10; i++ )
cout << myArray[i] << " ";
return 0;
}

输出:

1 2 3 7 7 7 7 8 9 10

关于c++ - 如果有重复值,快速排序无限循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20355634/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com