无法快速排序变得稳定排序？

Question

方法1

CAR 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

为了基本上尽量让它稳定的排序,而是j指向最后一个索引(listSize-1),如果j点listSize/2(即mid),那么,

我们进入场景, j > high或者i >= mid,哪里a[i]没有对应a[j]的交换,反之亦然.在这样的情况下,换a[i]用a[pivot]也没有意义,这看起来不正确的做法,要确认相同,

---

我的问题:

方法2,

通过保持快速排序的本质,我们不能用pivot元素(在任何索引处)进行分区吗？

注意:分析快速排序,而不是家庭作业

Answer 1

这看起来像家庭作业,所以我不打算完全解决它:

• 通过确保没有2个元素相等,可以使快速排序稳定.

• 单独选择不同的枢轴并不能为此提供解决方案.

既然你说这不是作业,这里是如何使快速排序稳定:

• 创建一个指向原始数组的指针数组.

• 使用quick-sort对这个数组进行排序,该函数用这种方式比较指向的值:

  int sortptr(const void *a, const void *b) {
      const my_type * const *pa = a;
      const my_type * const *pb = b;
      int cmp = original_compare_function(*pa, *pb);
      return cmp ? cmp : (pa > pb) - (pa < pb);
  }
  

• 将已排序的项目复制到已排序的数组中.

请注意,这种方法可以在适当的位置工作,但这样做很棘手,并且仍然需要分配指针数组.merge-sort对于稳定排序更加可靠,但需要大约原始数组大小一半的工作空间.