排序算法的稳定性分析（含java代码）
首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。
其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些（个人感觉，没有证实）。
一个班的学生已经按照学号大小排好序了，我现在要求按照年龄从小到大再排个序，如果年龄相同的，必须按照学号从小到大的顺序排列。
那么问题来了，你选择的年龄排序方法如果是不稳定的，是不是排序完了后年龄相同的一组学生学号就乱了，你就得把这组年龄相同的学生再按照学号拍一遍。
如果是稳定的排序算法，我就只需要按照年龄排一遍就好了。
这样看来稳定的排序算法是不是节省了时间。稳定性的优点就体会出来了。
回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
//冒泡排序
public static void bubbleSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
arr[j+1]=arr[j]+arr[j+1]-(arr[j]=arr[j+1]);
}
}
}
}(2)选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
//选择排序1
public static void selectSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
arr[i]=arr[i]+arr[j]-(arr[j]=arr[i]);
}
}
}
}(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
（12345|5:多次比较后，前面12345已经有序，5不比5小，所以不插到其前）
//插入排序:1.选取数据2.比较右移3.插入数据
public static void insertSort(int[] arr){
int select=0;
for(int i=1;i<arr.length;i++){
select=arr[i];
int j=0;
for(j=i;j>0&&arr[j-1]>=select;j--){//大小大，变成小大大
//往前比较，遇到比select大的值，插入到其前
arr[j]=arr[j-1];//以前的值右移，空出位置给select
}
arr[j]=select;
}
}(4)快速排序
以Ai与Aj为例子
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，
其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的
j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，
i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。
交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的
时候，很有可能把前面的元素的稳定性打乱，比如序列5 3 3 4 3 8 9 10 11，
现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱
，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。
//快速排序
//核心排序算法
public static void sortCore(int[] arr,int startIndex,int endIndex){
if(startIndex>=endIndex){
return;
}
int boundary=boundary(arr,startIndex,endIndex);
sortCore(arr,startIndex,boundary);
sortCore(arr,boundary+1,endIndex);
}
//左右两区部分数据 交换并返回分界点
private static int boundary(int[] arr, int start, int end) {
int standard=arr[start];//定义标准，即最左元素
int leftIndex=start;//左指针
int rightIndex=end;//右指针
while(leftIndex<rightIndex){
while(leftIndex<rightIndex && arr[rightIndex]>=standard){
rightIndex--; //从右向左查找
}
arr[leftIndex]=arr[rightIndex];//小于基准的移到左端
//（把第三个3移到最前面）
while(leftIndex<rightIndex && arr[leftIndex]<=standard){
leftIndex++;//从左往右查找
}
arr[rightIndex]=arr[leftIndex];//大于基准的移到右端
}
arr[leftIndex]=standard;//基准位置不再变化,基准值来到中间
return leftIndex;
}(5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
如果说稳定性破坏，那只能是在合并的过程中。
在合并的过程中，2个元素如果相等我们始终会先将左边子数组的元素先放入原数组当中，这样就不会破坏稳定性
如我们将{1,3,5,3,6,9}排序，在{1,3,5}和{3,6,9}合并的过程中，左边的元素3先放入数组中
//归并排序
public static void mergeSort(int[] arr){
//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
int[] temp=new int[arr.length];
sort(arr,0,arr.length-1,temp);
}
public static void sort(int[] arr,int left,int right,int[] temp){
if(left<right){
int mid=(left+right)/2;
sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i=left;//左序列指针
int j=mid+1;//右序列指针
int t=0;
while(i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++]=arr[i++];
}else{
temp[t++]=arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++]=arr[i++];
}
while(j<=right){//将右边剩余元素填充进temp中
temp[t++]=arr[j++];
}
t=0;
//将temp中的元素全部拷贝到原数组中
while(left<=right){
arr[left++]=temp[t++];
}
}(6)基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
//基数排序
/**
* @param arr 待排序数组
* @param radix 基数（10，盒子个数）
* @param d 待排序中，最大的位数
* */
public static void radixSort(int[] arr,int radix,int d){
int length=arr.length;
int[] temp=new int[length];//用于暂存元素
int[] count=new int[radix];//用于记录待排序元素的信息,用来表示该位是i的数的个数
int divide=1;
for(int i=0;i<d;i++){
//重置count数组，开始统计下一个关键字
Arrays.fill(count,0);
//将arr中的元素完全复制到temp数组中
System.arraycopy(arr,0,temp,0,length);
//计算每个待排序数据的子关键字
for(int j=0;j<arr.length;j++){
int subKey=(temp[j]/divide)%radix;
count[subKey]++;
}
//统计count数组的前j位（包含j）共有多少个数
for(int j=1;j<radix;j++){
count[j]=count[j]+count[j-1];
}
//按子关键字对指定的数据进行排序，因为开始是从前往后放，现在从后往前读取，保证基数排序的稳定性
for(int j=arr.length-1;j>=0;j--){
int subKey=(temp[j]/divide)%radix;
count[subKey]--;
arr[count[subKey]] = temp[j];
//插入到第--count[subKey]位，因为数组下标从0开始
}
divide = divide * radix; // 1 10 100
}
}(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
//希尔排序
public static void shellSort1(int[] arr){
//增量gap，并逐渐缩小增量
for(int gap=arr.length/2;gap>0;gap/=2){
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for(int i=gap;i<arr.length;i++){
int j=i;
while(j-gap>=0 && arr[j]<arr[j-gap]){
//插入排序采用交换法
swap(arr,j,j-gap);
j-=gap;
}
}
}
}
(8)堆排序
我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， … 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
//堆排序
public static void heapSort(int[] arr){
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子节点从下至上、从右至左调整结构
adjustHeap(arr, i, arr.length - 1);
}
//2.调整堆结构，交换堆顶元素和末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
}
}
//调整大顶堆（此时大顶堆已构建完成）
private static void adjustHeap(int[] arr, int i, int end) {
int temp=arr[i];//取出当前元素
for(int k=i*2+1;k<=end;k=k*2+1){
//从i结点的左子节点开始，也就是2*i+1
if(k+1<=end && arr[k]<arr[k+1]){
//如果左子节点<右子节点，k指向右子节点
k++;
}
if(arr[k]>temp){
//如果子节点＞父节点，将子节点值赋给父节点
arr[i]=arr[k];
i=k;
}else{
break;
}
}
arr[i]=temp;//将temp值放到最终的位置
}综上，得出结论:
不稳定：选择排序、快速排序、希尔排序、堆排序
稳定：冒泡排序、插入排序、归并排序和基数排序
关于排序方法的选择：
- (1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
- 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
- (2)若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；
- (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。