3

我知道有几个类似的帖子，但没有一个答案令人满意，这就是我想再次问这个问题的原因。

考虑下面的代码。这是我根据 CRLS Introduction to Algorithms 实现的快速排序

int partition(int* a, int s, int e)
{
    int pivot = a[e];
    int q = s-1;
    for (int i = s; i <= e; i++)
    {
        if (a[i] <= pivot) {
            q++;
            int tmp = a[q];
            a[q] = a[i];
            a[i] = tmp;
        }
    }
    return q;
}

void quickSort(int* a, int s, int e)
{
    if (e > s) {
        int q = partition(a, s, e);
        quickSort(a, s, q-1);
        quickSort(a, q+1, e);
    }
}

稳定的排序算法保持具有相同键（即值）的记录的相对顺序。我不明白为什么快速排序不是其中之一。尽管其中不相邻的元素之间存在交换，但我仍然不明白为什么会导致不稳定。我真的希望有人可以举出例子来解释这一点。

谢谢你。

4

2 回答 2

2

在稳定的排序算法中，交换或弹簧只发生在相邻元素中。例如在合并排序中，元素被制成一个单元，然后使用合并函数进行相应的排序。我认为如果你考虑线性排序，它是不言自明的。但在快速排序中并非如此。

于 2015-06-21T13:59:14.693 回答
0

尝试 [ 1,1,1,5,5,5,5, 1 ,1,1,4]，pivot 是 4 ，当我遇到更强的“1”时，它会用这个“1”交换前 5 个

于 2017-06-26T09:00:49.633 回答