如果排序算法保留具有 equals 键的任意两个元素的相对顺序,则该算法是稳定的。快速排序在什么条件下稳定?
当没有项被传递时,快速排序是稳定的,除非它具有较小的键。
还有哪些条件可以使其稳定?
嗯,使用 O(N) 空间而不是就地不稳定实现使用的 O(log N) 空间来创建稳定的快速排序是相当容易的。当然,使用 O(N) 空间的快速排序不一定是稳定的,但可以使其稳定。
我读过,可以使用 O(log N) 内存进行就地快速排序,但最终会明显变慢(并且实现的细节有点糟糕)。
当然,您始终可以遍历正在排序的数组并添加一个额外的键,该键是其在原始数组中的位置。然后快速排序就会稳定,你只需遍历并在最后删除多余的键即可。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)