Quicksort进入无限循环

Question

我正在尝试编写quicksort的代码,但它继续在infinte循环,我已经努力在下面的代码中找到错误,任何人都可以帮助请.

#include<stdio.h>
#include<stdlib.h>

int arr[100];

void quicksort(int low,int high)
{
    int i = low,j = high,pivotIndex,pivot;
    pivotIndex = rand()%20;
    pivot = arr[pivotIndex];

    if(i>=j)
        return;

    while(i<j)
    {

        while(arr[i]<pivot && i<j)
        {
            i++;
        }

        while(arr[j]>pivot && j>i)
        {
            j--;
        }

        if(i<j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

    }
    quicksort(low,i);
    quicksort(i+1,high);
}

int main()
{
    int i,j,temp;

    for(i=0;i<20;i++)
        arr[i] = rand()%21;

    for(i=0;i<20;i++)
        printf("%d ",arr[i]);
    printf("\n");

    quicksort(0,19);

    for(i=0;i<20;i++)
            printf("%d ",arr[i]);
    printf("\n");

    return 0;
}

Answer 1

您的数据透视表选择错误,您应该在(索引)范围内[low,high)选择一个数据透视表,同时在范围内选择一个数据透视表[0,20):

pivotIndex = rand()%20;

它稍后会使分区不顺利,而i后来用于递归的值将是错误的.

编辑:

还有一个问题是分区,它还应该考虑如何处理pivot元素及其重复项 - 应该有某种"tie breaker" - pivot应该转到数组的一侧(或者某种替代方案).
例如,假设枢轴是5,并且数组是[5,3,8,5]:
您将无限地交替5次反复交换,这是绝对错误的.