前言

虽然很早的算法课、书上早就了解了关于算法稳定性的内容，google一搜相关总结也一大篇，但是由于作者在生活中应用到的稳定性的例子很少，光靠记忆几天估计就忘了，所以这次专门抽了点时间研究了下，主要想弄明白两个问题：

• 如何分析一个算法的稳定性
• 算法稳定性能给实际开发中带来哪些益处（算法稳定性的意义）

稳定性的定义

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序中，Ai=Aj，且Ai在Aj之前，在排序后的序列中，Ai仍在Aj之前，则称这种排序算法是稳定的；否则该算法是不稳定的。

简单的总结

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法；
冒泡排序、插入排序、归并排序和基数排序都是稳定的排序算法。

判断方法

对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意：排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成 a[j].key>=a[j+1].key，则两个相等的记录就会交换位置。

void BubbleSort(DataType a[], int n)
  { int i, j, flag = 1;
DataType temp;
for(i = 1; i < n && flag == 1; i++)
{ flag = 0;
for(j = 0; j < n-i; j++)
{ 
if(a[j].key >a[j+1].key) /*如果改为a[j].key >=a[j+1].key，就变不稳定了*/
{   
flag = 1;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp; }
}
}
}   

如何进行稳定性分析

作者不喜欢死记，所以这里举个例子，一起分析。从上面介绍看出，算法的稳定性最主要的决定于我们怎么写，这里用一个简单的选择排序例子。代码如下：

/**
 * 简单直观的选择排序
* @param a 待排序数组
* @param length 数组长度
 */
public static void selectSort(int[] a, int length) {
    for (int i = 0; i < length; i++) {
        for (int j = i +1; j < length; j++) {
            if (a[i] > a[j]) {
                swap(a, i, j);
            }
        }
    }
}

选择排序即是给每个位置选择待排序元素中当前最小的元素。比如给第一个位置选择最小的，在剩余元素里面给第二个位置选择次小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在选择时，如果当前锁定元素比后面一个元素大，而后面较小的那个元素又出现在一个与当前锁定元素相等的元素后面，那么交换后位置顺序显然改变了。举个例子：

2 5 2 1 8

我们知道第一趟选择第1个元素2会与1进行交换，那么原序列中两个2的相对先后顺序也就被破坏了（加粗的2跑到后面去了）。变为了如下序列：

1 5 2 2 8

所以选择排序也就是不稳定的。通过分析我们发现分析稳定性涉及（只是涉及，并不是至关重要，后面会讲到）两个方面：

• swap的次数
• 多key情况下，涉及其他值得顺序：例如学生按照年龄由高到低，我还想他们学号从小到大，跟最初学号顺序尽可能一致

稳定性的意义

1、如果只是简单的进行数字的排序，那么稳定性将毫无意义。
2、如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（正如上面说的，会增大一定的开销，但并不起决定性因素，算法本身的开销才是关键——比如换种算法）
3、如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
4、除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。

总结

• 如何分析算法稳定性：将算法一步的拆分，分析其原理会不会导致不稳定的因素
• 算法的意义：深入了解一个算法，会分析其造成不稳定的因素是有意义的，但不要苛求这种意义能为这种算法提升多大的效益