稳定排序算法图文详解

作者: 冉小歌F
来源: 51数据库
2022-09-23

当待排序序列中含有相同元素时，如果排序算法完成排序的同时，能保证相同元素的相对位置不发生改变，我们可以说这个排序算法是稳定的，或者说该排序算法是一个稳定排序算法。

举个例子，假设待排序序列为 {3,1,2,4,2}，序列中包含两个相同的元素 2，它们的相对位置为：绿色元素 2 位于红色元素 2 的左侧。如果我们选用的排序算法对该序列进行升序或者降序排序后，新序列中绿色元素 2 仍位于红色元素 2 的左侧，那么这个排序算法就是一个稳定排序算法。

再举个例子，下图描述了稳定排序算法和非稳定排序算法的区别：

其中，3、3'、3'' 为相同元素，5、5' 也是相同元素。

可以看到，排序前 3'' 位于 3' 的右侧，3' 位于 3 的右侧，5' 位于 5 的右侧。如果排序后各相同元素的相对位置都不改变，则所用排序算法就是一个稳定排序算法；反之，如果相同元素的相对位置发生了改变，所用的排序算法就不能称为稳定排序算法。

了解完稳定排序算法之后，您还有必要了解什么是就地排序算法。和稳定排序算法类似，就地排序算法并非某种具体的排序算法，它描述的是符合以下条件的排序算法：