我的 QuickSort 代码有时运行但有时不会，我不知道错误发生在哪里

Question

int partition(int list[], int left, int right) {
    int low = left + 1;
    int high = right;
    int pivot = list[left];

    while (low < high) {
        while (low <= right && list[low] < pivot) {
            low++;
        }
        while (high >= left && list[high] > pivot) {
            high--;
        }
        if (low < high) Swap(&list[low], &list[high]);
    }
    Swap(&list[high], &list[left]);
    return high;
}

void quicksort(int list[], int left, int right) {
    if (left <= right) {
        int p = partition(list, left, right);
        quicksort(list, left, p - 1);
        quicksort(list, p + 1, right);
    }
}

这段代码有时能很好地排序，但有时不能产生任何后果，运行势不可挡。我应该修哪一部分？

Answer 1

问题是当函数分区遇到只有两个元素的数组时。在这种情况下，如果第一个元素小于第二个元素，最后的交换调用将随机排列数组。

您需要检查掉期是否合理：

if( list[high] < list[left] )
{
    Swap( &list[high] , &list[left] );
}

在最内层循环中交换变量 low 和 high 之后，您还需要递增和递减变量：

if (low < high) 
{
    Swap(&list[low], &list[high]);
    low++;
    high--;
}

而且 high 应该停在 left+1，而不是这里的 left:

 while (high >= left &&

Answer 2

你的partition()有缺陷

    while (low < high) {
        while (low <= right && list[low] < pivot) {
            low++;
        }
        while (high >= left && list[high] > pivot) {
            high--;
        }
        if (low < high) Swap(&list[low], &list[high]);
    }

如果 list[low] 和 list[high] 与 pivot 具有相同的值，这将产生一个无限循环。

我的 QuickSort 代码有时运行但有时不会，我不知道错误发生在哪里

My QuickSort code sometimes run but sometimes it does not and I don't know where error got happened

c

algorithm

quicksort

data-structures

我的 QuickSort 代码有时 运行 但有时不会，我不知道错误发生在哪里

My QuickSort code sometimes run but sometimes it does not and I don't know where error got happened

c

algorithm

quicksort

data-structures

我的 QuickSort 代码有时运行但有时不会，我不知道错误发生在哪里