快速排序的实现 [英] Implementation of Quick Sort

问题描述

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

我已经编写了一个实现Quick sort的程序.但是该程序进入了无限循环.在Quicks函数中，用于递增和递减i和j的while循环是问题.快速排序.

Hi, I have written a program to implement Quick sort.But the program is going into an infinite loop.In the Quicks function,the while loops for incrementing and decrementing i and j are the problem.Can anybody tell me what is wrong with this Implementation of QUick Sort.

推荐答案

使用输入和算法进行快速试运行，您会发现一段时间后会陷入无限循环.

Do a quick dry run using your input and the algorithm, you'll notice you run into an infinite cycle after a while.

您正在从quicks(arr,7,0,1,6);开始循环.尝试通过将low设置为最右边"的元素(即0)来解决此问题.由于算法似乎确实存在缺陷，high的位置根本没有变化，因此我一直将其移至high，因此这绝对不能解决您的问题.您正在尝试使一个非常简单的任务复杂化.

You are starting the loop from quicks(arr,7,0,1,6);. Try instead by setting low to the "rightmost" element, that is 0. This won't definitely solve your problem as the algorithm seems really flawed, with the position of high not changing at all, and i moving all the way to high. You're trying to complicate a very simple task.

i将从lo变为pivot.而j从hi到pivot.找到pivot正确的位置后，您将把pivot和lo向前移动1，然后重复该过程.

i would go from lo to pivot. And j from hi to pivot. After the pivot is found to be in the right place, you'll move forward pivot and lo by 1, and repeat the process.

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

Take a look at this image, you'll get an idea of the algo required:

这篇关于快速排序的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！