当待排序序列中含有相同元素时,如果排序算法完成排序的同时,能保证相同元素的相对位置不发生改变,我们可以说这个排序算法是稳定的,或者说该排序算法是一个稳定排序算法。
举个例子,假设待排序序列为 {3,1,2,4,2},序列中包含两个相同的元素 2,它们的相对位置为:绿色元素 2 位于红色元素 2 的左侧。如果我们选用的排序算法对该序列进行升序或者降序排序后,新序列中绿色元素 2 仍位于红色元素 2 的左侧,那么这个排序算法就是一个稳定排序算法。
再举个例子,下图描述了稳定排序算法和非稳定排序算法的区别:
其中,3、3'、3'' 为相同元素,5、5' 也是相同元素。
可以看到,排序前 3'' 位于 3' 的右侧,3' 位于 3 的右侧,5' 位于 5 的右侧。如果排序后各相同元素的相对位置都不改变,则所用排序算法就是一个稳定排序算法;反之,如果相同元素的相对位置发生了改变,所用的排序算法就不能称为稳定排序算法。
了解完稳定排序算法之后,您还有必要了解什么是就地排序算法。和稳定排序算法类似,就地排序算法并非某种具体的排序算法,它描述的是符合以下条件的排序算法:
直接对待排序序列做修改,而不是创建一个新的排序序列;
实现排序的整个过程,仅使用少量的额外空间;
排序过程仅通过交换元素的方式实现;
前面章节中,我们学习了冒泡排序、插入排序、选择排序、归并排序、快速排序等多种排序算法,其中有些排序算法可以称为稳定排序算法,有些称为就地排序算法,如表 1 所示。
排序算法 | 就地排序算法 | 稳定排序算法 |
---|---|---|
冒泡排序算法 | Y | Y |
插入排序算法(希尔排序算法) | Y | Y |
选择排序算法 | Y | N |
归并排序算法 | N | Y |
快速排序算法 | Y | N |
Y 表示可以,N 表示不可以。