sorting - 快速排序的实现

Question

#include<stdio.h>
#include<iostream.h>
#include<conio.h>

void quicks(int *arr,int x,int pivot,int lo,int hi);
void swap1(int *x,int *y);
int main()
{
int *arr = new int[7];
arr[0] = 23;
arr[1] = 3;
arr[2] = -23;
arr[3] = 45;
arr[4] = 12;
arr[5] = 76;
arr[6] = -65;
quicks(arr,7,0,1,6);
for(int i = 0;i<7;i++)
    std::cout << arr[i] <<"\t";
getch();
return 0;
 }
 void quicks(int *arr,int x,int pivot,int lo,int hi)
 {
int i = lo,j = hi;
if(pivot < x-1)
{
while(i <= hi)
{
    if(arr[i] <= arr[pivot])
        i++;
    else
        break;
}
while(j >= lo)
{
    if(arr[j] >= arr[pivot])
        j--;
    else    
        break;
}
if( i > j)
{
    swap1(&arr[j],&arr[pivot]);
    lo = pivot+1;
    hi = x - 1;
    quicks(arr,x,pivot,lo,hi);
}
else if(i == j)
{
    pivot = pivot + 1;
    lo = pivot+1;
    hi = x - 1;
    quicks(arr,x,pivot,lo,hi);
}
else if(i < j)
{
    swap1(&arr[j],&arr[i]);
    lo = i + 1;
    hi = j - 1;
    quicks(arr,x,pivot,lo,hi);
}
}
else
{
    printf("\nDONE\n");
}
}

void swap1(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}

嗨，我写了一个程序来实现快速排序。但是程序进入了一个无限循环。在 Quicks 函数中，用于递增和递减 i 和 j 的 while 循环是问题。谁能告诉我这有什么问题快速排序的实现。

Answer 1

使用您的输入和算法进行快速试运行，您会注意到一段时间后您会进入无限循环。

您正在从 开始循环quicks(arr,7,0,1,6);。尝试通过将“最右边”元素设置为低，即 0。这肯定不能解决您的问题，因为该算法似乎确实存在缺陷，高的位置根本没有改变，并且我一直移动到高。你试图使一个非常简单的任务复杂化。

i会从lo到pivot。j从hi到pivot。_ 找到正确的位置后pivot，您将向前移动1，pivot并lo重复该过程。

看一下这张图片，您将了解所需的算法：