快速排序不能变成稳定排序吗？

Question

方法1

C.A.R . Hoare介绍了分区逻辑(如下所示)，这是在学校教的，

low = pivot = 0;
i = 1;
j = high = listSize-1;

while (true) {
    while (a[i] <= a[pivot] && (i < high)) {
        i = i + 1;
    }
    while (a[j] >= a[pivot] && (j > low)) {
        j = j - 1; 
    }

    if (i >= j)
        break;
    swap(a[i], a[j])
}

swap(a[j], a[pivot]); // pivot element is positioned(once)
return j;

方法2

如果指向listSize/2(即mid)，则j指向最后一个索引(listSize-1)，则基本上尝试将其排序为j (即mid)，

我们进入了j > high或i >= mid的场景，其中a[i]没有相应的a[j]交换，反之亦然。在这种情况下，将a[i]与a[pivot]交换也是没有意义的，(它看起来是不正确的方法)来确认相同，

我的问题是：

使用方法2，

通过维护快速排序的本质，我们不能用枢轴元素(在任何索引上)进行分区吗？

注意:分析快速排序，而不是在家工作。

Answer 1

这看起来像在家工作，所以我不会完全解决这个问题：

• 通过确保任何2个元素的比较相等，可以使快速排序变得稳定.
• 单独选择不同的枢轴并不能提供解决方案。

既然你说这不是家庭作业，下面是如何使快速排序稳定：

• 创建指向原始数组的指针数组。
• 使用快速排序方法对此数组进行排序，并以这样的方式对指向值进行比较： { const my_type * const *pa = a；const my_type * const *pb = b；int cmp = original_compare_function(*pa，*pb)；返回cmp？cmp：(pa > pb) - (pa < pb)；}
• 将已排序的项复制到排序数组中。

请注意，这种方法可以在适当的地方工作，但是这样做是很困难的，并且仍然需要分配指针数组。合并排序对于稳定排序来说要可靠得多，但需要的工作空间大约是原始数组大小的一半。