如果排序算法使用等于键保留任何两个元素的相对顺序,则它是稳定的.在哪些条件下快速稳定？
没有项目通过时,Quicksort是稳定的,除非它有一个较小的键.
还有什么其他条件可以稳定？
Jus*_*eel 13
好吧,使用O(N)空间而不是就地,不稳定实现使用的O(log N)来制作稳定的快速排序是非常容易的.当然,使用O(N)空间的快速排序不一定是稳定的,但可以这样做.
我已经读过可以制作一个使用O(log N)内存的就地快速排序,但它最终会慢得多(并且实现的细节有点野蛮).
当然,您可以随时查看正在排序的数组,并添加一个额外的键,它是原始数组中的位置.然后快速排序将是稳定的,您只需通过并在最后删除额外的密钥.
条件很容易弄清楚，只需保持相等元素的原始顺序即可。没有其他条件与此条件有本质区别。关键是如何实现它。
有一个很好的例子。
1. 使用中间元素作为枢轴。
2. 创建两个列表，一个用于较小的，另一个用于较大的。
3. 从第一个到最后一个迭代，将元素放入两个列表中。将小于或等于并位于主元之前的元素附加到较小的列表中，将大于或等于并位于主元之后的元素添加到较大的列表中。继续递归较小的列表和较大的列表。
https://www.geeksforgeeks.org/stable-quicksort/
后2点都是必要的。作为枢轴的中间元素是可选的。如果您选择最后一个元素作为主元，只需从头开始将所有相等的元素逐个附加到较小的列表中，它们将保持原始顺序。