如果有重复值，则快速排序无限循环

本文介绍了如果有重复值，则快速排序无限循环的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有一个快速排序程序，工作伟大，直到我尝试排序具有重复数字的数组。程序陷入无限循环。我相信这发生在 While（lower< upper）代码块中。

code> void quickSort（int array []，int size）{ if（size< 2）return; int pivot，lower，upper，temp; //设置第一个和最后一个元素的缩进 lower = 0; upper = size - 1; //随机选择枢轴元素 pivot = array [rand（）％（size）]; while（lower< upper）{ // Lower必须是数字<而不是一个数字> = pivot while（array [lower]< pivot）{ lower ++; } while（array [upper]> pivot）{ upper--; } //上下交换 temp = array [lower]; array [lower] = array [upper]; array [upper] = temp; } //递归地对数组的两个分区重复过去的操作 quickSort（array，lower）; quickSort（& array [lower + 1]，size-lower-1）; }

解决方案

/ p>

从维基百科，就地快速排序的伪代码如下： （不是说他们应该盲目信任）

function quicksort（array）如果length（array）> 1 pivot：=选择数组中的任何元素 left：=数组的第一个索引 right：=数组的最后一个索引 while left right right while array [左] pivot left：= left + 1 while array [right]> pivot right：= right - 1 如果left≤right swap数组[left] with数组[right] left：= left + 1 right： right-1 quicksort（从第一个索引到右侧的数组） quicksort（数组从左到上索引）

因此，您看到它与您的算法非常相似，只需稍加修改。

while < = upper）{

此外，只有当

您的代码在递归调用中有所不同：

quicksort（数组从第一个索引到右侧）{array [0]到array [upper]} quicksort这是因为现在它已经退出while循环了，因为它已经退出了一个循环。

#include< iostream> #include< cstdlib> using namespace std; void quickSort（int array []，int size）{ if（size< 2）return; int pivot，lower，upper，temp; //设置第一个和最后一个元素的缩进 lower = 0; upper = size - 1; //随机选择枢轴元素 pivot = array [rand（）％（size）]; while（lower< = upper）{ // Lower必须是数字<而不是一个数字> = pivot while（array [lower]< pivot）{ lower ++; } while（array [upper]> pivot）{ upper--; } //交换上下 if（lower< = upper）{ temp = array [lower]; array [lower] = array [upper]; array [upper] = temp; lower ++; upper--; } } //递归地对数组的两个分区重复过去的操作 quickSort（array，upper + 1）; quickSort（& array [lower]，size-lower）; } int main（）{ //你的代码在这里 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

I have a quicksort program that works great until I try to sort an array that has a repeating number. The program gets stuck in an infinite loop. I believe this is happening in the While(lower < upper) block of code.

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); }

解决方案

EDIT: Code added.

From Wikipedia, the pseudo-code for in-place quicksort is as follows: (Not saying that they should be trusted blindly)

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)

So you see it is quite similar to your algorithm, with minor modifications.

while(lower <= upper){

Also you need to swap only if lower <= upper and then update the indices.

And your code differs in the recursive calls:

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]}

This is because now that it has exited the while loop, upper is less than lower.

Full working code:

#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; }

Output:

1 2 3 7 7 7 7 8 9 10