快速排序 - 使其稳定的条件
如果排序算法保留具有 equals 键的任意两个元素的相对顺序，则该算法是稳定的。在什么条件下快速排序是稳定的？
当没有项被传递时，快速排序是稳定的，除非它有一个较小的键。
还有哪些条件可以使其稳定？
A sorting algorithm is stable if it preserves the relative order of any two elements with equals keys. Under which conditions is quicksort stable?
Quicksort is stable when no item is passed unless it has a smaller key.
What other conditions make it stable?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
嗯，使用 O(N) 空间而不是就地不稳定实现使用的 O(log N) 空间来创建稳定的快速排序是相当容易的。当然，使用 O(N) 空间的快速排序不一定是稳定的，但可以使其稳定。
我读过，可以使用 O(log N) 内存进行就地快速排序，但最终会明显变慢（并且实现的细节有点糟糕）。
当然，您始终可以遍历正在排序的数组并添加一个额外的键，该键是其在原始数组中的位置。然后快速排序就会稳定，你只需遍历并在最后删除多余的键即可。
Well, it is quite easy to make a stable quicksort that uses O(N) space rather than the O(log N) that an in-place, unstable implementation uses. Of course, a quicksort that uses O(N) space doesn't have to be stable, but it can be made to be so.
I've read that it is possible to make an in-place quicksort that uses O(log N) memory, but it ends up being significantly slower (and the details of the implementation are kind of beastly).
Of course, you can always just go through the array being sorted and add an extra key that is its place in the original array. Then the quicksort will be stable and you just go through and remove the extra key at the end.
条件很容易算出来，只需保持相等元素的原始顺序即可。没有其他条件与此有本质区别。重点是如何实现。
有一个很好的例子。
1.使用中间元素作为枢轴。
2.创建两个列表，一个用于较小的列表，另一个用于较大的列表。
3.从第一个到最后一个迭代，将元素放入两个列表中。将小于或等于主元之前的元素追加到较小的列表中，将大于或等于主元之后的元素追加到较小的列表中更大的列表。继续递归较小的列表和较大的列表。
https://www.geeksforgeeks.org/stable-quicksort/
后两点都是必要的。作为枢轴的中间元素是可选的。如果选择最后一个元素作为主元，只需从头开始将所有相等的元素逐一附加到较小的列表中，它们将保持原始顺序。
The condition is easy to figure out, just keep the raw order for equal elements. There is no other condition that has essential differences from this one. The point is how to achieve it.
There is a good example.
1. Use the middle element as the pivot.
2. Create two lists, one for smaller, the other for larger.
3. Iterate from the first to the last and put elements into the two lists. Append the element smaller than or equals to and ahead of the pivot to the smaller list, the element larger than or equals to and behind of the pivot to the larger list. Go ahead and recursive the smaller list and the larger list.
https://www.geeksforgeeks.org/stable-quicksort/
The latter 2 points are both necessary. The middle element as the pivot is optional. If you choose the last element as pivot, just append all equal elements to the smaller list one by one from the beginning and they will keep the raw order in nature.
如果您的方法是这样的话，您可以将它们添加到列表中：
You can add these to a list, if that's your approach: