堆排序，快速排序稳定性

Question

我尝试过具有 2或3个元素等于的数组所有元素都等于此 [2,2,2,2,2,2,2]，它是稳定还是不？当然，通过使用堆排序或快速排序。

谢谢。

Answer 1

给定数据集的稳定性取决于实现详细信息。例如，查看Wiki Page的Lomuto分区

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] < pivot then
            i := i + 1
            swap A[i] with A[j]
    swap A[i + 1] with A[hi]
    return i + 1

我们可以看到i永远不会增加，因此最后交换交换了第一个和最后一个范围的项目，打破了初始顺序。

从同一页面上实现Hoare分区似乎没有破坏顺序