c# - 这个 QuickSort 程序有什么问题？

Question

我已经根据给我的伪代码编写了一个快速排序算法。 我已经运行了大约 4 个小时的输出，但我似乎无法确切地找到我的算法开始脱轨的原因。这种收集逻辑是我难以解决的问题。

无论如何，每当我运行我的程序时，都会有 3 种可能的结果:

1. 该列表经过整理且 100% 正确。
2. 列表的 90% 已整理完毕，其中有一对或两对元素不完整。
3. 该列表从未排序并导致无限循环。

鉴于我的结果，它让我相信某些事情与我正在使用的 index 变量有关。但是，我无法弄清楚为什么或出了什么问题。

这是我用于快速排序算法的所有代码:

public void QuickSort(IList<int> list, int l, int r)
    {
        if (l>=r) return; 
        int index = Partition(list, l, r);
        Console.WriteLine("index: " + index);
        QuickSort(list, l, (index-1));
        QuickSort(list, (index+1), r);
    }

    public int Partition(IList<int> list, int l, int r)
    {
        int pivot = list[l];
        int i = l;
        int j = r + 1;
        do 
        {
            do { i++; } while(i < list.Count && list[i] < pivot);
            do { j--; } while(j > 0 && list[j] >= pivot);
            Swap(list, i, j);
        } while(i<j);
        Swap(list, i ,j);
        Swap(list, j, l);
        return j;
    }

    public void Swap(IList<int> list, int i, int j)
    {
        //Console.WriteLine("Swapping [i] " + list[i] + " with [j] " + list[j]);
        //PrintList(list, i, j, false);
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
        //PrintList(list, j, i, true);

    }

PrintList 只是用来测试我的输出。

这是一个示例输入/输出:

输入: [18,43,5,73,59,64,6,17,56,63]

输出:[5,6,18,17,43,59,56,63,64,73]

Answer 1

一个问题在于您的分区方法，您有:

    int i = l;
    int j = r + 1;
    do 
    {
        do { i++; } while(i < list.Count && list[i] < pivot);
        do { j--; } while(j > 0 && list[j] >= pivot);
        Swap(list, i, j);
    } while(i<j);

如果您输入 l == 0 ，那么第一次循环时，您将增加 i ，检查的第一项是 list[1] 。您可能想要那些 do循环为while循环。

另一个问题是你无条件交换 list[i]和list[j]在你的循环中，即使 list[i] <= list[j] 。在进行交换之前您可能应该检查一下。

这并不能解决您的所有问题，但它会为您指明正确的方向。