c++ - QuickSort 代码无法正常工作

Question

int main()
    {
        int numbers[size] = {14, 7, 23, 31, 1, 20, 6, 3, 40, 5}, start, finish;

        cout << "Numbers are: " << endl;
        for (int i = 0; i < size; i++)
        {
            cout << numbers[i] << "\t";
        }

        finish = 10;
        start = 0;

        quickSort(numbers, start, finish);

        cout << "\n\nSorted: " << endl;
        for (int j = 0; j < size; j++)
        {
            cout << numbers[j] << "\t";
        }

        return 0;
    }

int Partition(int numbers[], int start, int finish)
{

    int pole = start;
    int pivot = numbers[finish];

    for (int k = 0; k < finish - 1; k++)
    {
        if (numbers[k] <= pivot)
        {
            int temp = numbers[k];
            numbers[k] = numbers[pole];
            numbers[pole] = temp;

            pole++;
        }
    }

    int temp2 = numbers[pole];
    numbers[pole] = numbers[pivot];
    numbers[pivot] = temp2;

    return pole;
}

void quickSort(int numbers[], int start, int finish)
{
    int marker;
    if (start < finish)
    {
        marker = Partition(numbers, start, finish);
        quickSort(numbers, start, marker - 1);
        quickSort(numbers, marker + 1, finish);
    }
}

我觉得我错过了什么，但我不知道是什么。该程序未正确排序。需要一些帮助!我试图在过程中找出问题所在，据我所知，它并没有完全解决问题。好吧，我自己也不确定。我还是递归的新手，所以我可能做错了什么。

Answer 1

代替

finish = 10;

你应该写

finish = size;

在你写的分区函数中

int pivot = numbers[finish];

这超出了数组的末尾。你的意思是

int pivot = numbers[finish - 1];

在你的分区函数中你运行这样一个循环:

for (int k = 0; k < finish - 1; k++)

即从整个数组的开头开始。应该是:

for (int k = start; k < finish - 1; k++)

你的分区函数的最后一步是错误的:

int temp2 = numbers[pole];
numbers[pole] = numbers[pivot];
numbers[pivot] = temp2;

使用枢轴值而不是枢轴索引。应该是:

int temp2 = numbers[pole];
numbers[pole] = numbers[finish - 1];
numbers[finish - 1] = temp2;

quickSort 的实现也是错误的:

marker = Partition(numbers, start, finish);
quickSort(numbers, start, marker - 1);
quickSort(numbers, marker + 1, finish);

应该是:

marker = Partition(numbers, start, finish);
quickSort(numbers, start, marker);
quickSort(numbers, marker + 1, finish);

---

以上更改修复了您的代码。

从根本上讲，我认为您需要更清楚地了解 start 和 finish 的含义。它们遵循这样的约定:start 是第一项的索引，finish 比最后一项的索引大一个。由于没有完全理解这个约定，上面的许多错误都归结为差一错误。