2

我正在尝试编写快速排序的代码，但它一直在无限循环中，我已经努力在以下代码中找到错误，任何人都可以帮忙。

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

3 回答 3

7

您的枢轴选择是错误的，您应该在 (index) range[low,high)中选择一个枢轴，而您在 range 中选择了一个枢轴[0,20)：

pivotIndex = rand()%20;

它稍后会使分区不顺利，并且i您稍后用于递归的 的值 - 将是错误的。

编辑：

另一个问题是分区，它还应该考虑如何处理枢轴元素及其副本 - 应该有某种“决胜局” - 枢轴应该转到数组的一侧（或其他替代方案）。
例如，假设枢轴是5并且数组是[5,3,8,5]：
您将一遍又一遍地无限交换 5，这绝对是错误的。

于 2012-10-31T08:32:30.210 回答
1

作为排序插件的作者，我可以向您保证，重新发明这些算法真的会像谚语一样咬住您。;o)

必须特别注意（如前所述）选择枢轴，算术将如何影响枢轴值（例如，VBA 在浮点中进行整数运算，导致各种奇怪），其中“剩菜”去吧，最后一步如何处理最后一个分区（你不会是第一个在这里跳过几条记录的人）。

这是许多语言的排序算法的链接：

http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

于 2012-10-31T11:05:06.563 回答
-1 
 pivotIndex = rand()%20;
 pivot = arr[pivotIndex];

每次调用快速排序时，您的 pivotIndex 可能不在范围内（低，高）。您可以使用

pivotIndex = low+rand()%(high-low);

我确信这将生成范围内的 pivotIndex。

于 2012-10-31T08:39:47.833 回答