首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。
 
  其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些（个人感觉，没有证实）。
 
回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。
 
(1)冒泡排序
 
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
 
(2)选择排序
 
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
 
(3)插入排序 
 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
 
(4)快速排序 
 快速排序有两个方向，左边的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] 交换的时刻。
 
(5)归并排序 
 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
 
(6)基数排序 
 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
 
(7)希尔排序(shell) 
 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
 
(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个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
 
综上，得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

 
 
 
 
  

   在下列排序方法中，不稳定的方法有
  
 
 
 
 
 
 
 正确答案: C   你的答案: C (正确)
 
 
 
  
归并排序与基数排序
 
 
 
 
 
  
插进排序与希尔排序
 
 
 
 
 
  
堆排序与快速排序
 
 
 
 
 
  
选择排序与冒泡排序
 
 
 
 
 
  
添加笔记
 
 收藏
 纠错
 
 
 
 

 
 
 

  这道题同：
 将一个从大到小的数组，用以下排序方法排序成从小到大的，（）最快。----阿里巴巴2015实习生笔试题
 
 
 
 
 
 
 排序方法        平均情况        最好情况        最坏情况        辅助空间        稳定性
 
 
 冒泡排序         O(n^2)           O(n)              O(n^2)            O(1)                稳定
 
 
 选择排序         O(n^2)          O(n^2)            O(n^2)            O(1)              不稳定
 
 
 插入排序         O(n^2)           O(n)              O(n^2)            O(1)                稳定
 
 
 希尔排序O(n*log(n))~O(n^2) O(n^1.3)       O(n^2)            O(1)              不稳定
 
 
 堆排序          O(n*log(n))     O(n*log(n))    O(n*log(n))       O(1)              不稳定
 
 
 归并排序       O(n*log(n))     O(n*log(n))    O(n*log(n))       O(n)                稳定
 
 
 快速排序       O(n*log(n))     O(n*log(n))      O(n^2)            O(1)              不稳定
 
 
 
 
 

  冒泡排序经过优化以后，最好时间复杂度可以达到O(n)。设置一个标志位，如果有一趟比较中没有发生任何交换，可提前结束，因此在正序情况下，时间复杂度为O(n)。
 
 
 
 
 

  选择排序在最坏和最好情况下，都必须在剩余的序列中选择最小（大）的数，与已排好序的序列后一个位置元素做交换，依次最好和最坏时间复杂度均为O(n^2)。
 
 
 
 
 

  插入排序是在把已排好序的序列的后一个元素插入到前面已排好序(需要选择合适的位置)的序列中，在正序情况下时间复杂度为O(n)。
 
 
 
 
 

  堆是完全二叉树，因此树的深度一定是log(n)+1，最好和最坏时间复杂度均为O(n*log(n))。
 
 
 
 
 

  归并排序是将大数组分为两个小数组，依次递归，相当于二叉树，深度为log(n)+1，因此最好和最坏时间复杂度都是O(n*log(n))。
 
 
 
 
 

  快速排序在正序或逆序情况下，每次划分只得到比上一次划分少一个记录的子序列，用递归树画出来，是一棵斜树，此时需要n-1次递归，且第i次划分要经过n-i次关键字比较才能找到第i个记录，因此时间复杂度是\sum_{i=1}^{n-1}(n-i)=n(n-1)/2，即O(n^2)。
 

 
 

 

冒泡排序
 
目录：
 1.原理
 2.代码实现
 3.时间复杂度
 4.稳定性
 5.应用
 
1.原理
 
试问冒泡排序谁不会？这篇文章重点不是叫你怎样写冒泡排序，而是总结了一点应用层面的东西。
冒泡排序的思想：挨个比较，两两比较，每一层循环会使得一个最大/小值到数组的最后面。就像一个个气泡被升上去一样，故名冒泡排序。
放原理图
 
 
2.代码实现
 
这是一种比较偷懒的方法，如果要代码更规范一些，可以考虑用函数和指针来实现
 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j;
    cin>>n;
    int arr[n+5];
    for(i=0;i<n;i++)cin>>arr[i];
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(arr[i]<arr[j])
            {
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }
    for(i=0;i<n;i++)
    {
        cout<<arr[i];
        if(i!=n-1)cout<<" ";
    }
    cout<<endl;
    return 0;
}

 
用函数解决代码如下
 
#include<bits/stdc++.h>
using namespace std;
void swapp(int *x,int *y)
{
    int temp=*x;
    *x=*y;
    *y=temp;
}
void maopaosort(int *a,int n)
{
    int j,i;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(a[i]<a[j])
            {
                swapp(&a[i],&a[j]);
            }
        }
    }
}
int main()
{
    int n,i;
    cin>>n;
    int arr[n+5];
    for(i=0;i<n;i++)cin>>arr[i];
    maopaosort(arr,n);
    for(i=0;i<n;i++)
    {
        cout<<arr[i];
        if(i!=n-1)cout<<" ";
    }
    cout<<endl;
    return 0;
}

 
3.时间复杂度
 
当数列是正序的时候，只需遍历一遍n-1个元素，没有移动次数，即最佳时间复杂度为O(n)
当数列是逆序的时候，冒泡排序总比较次数为n(n-1)/2，移动次数为3n(n-1)/2，最差时间复杂度为O(n^2)，
一般我们认为原始序列是杂乱的，我们认为算法的平均时间复杂度为O(n^2)
 
4.稳定性
 
因为算法只是元素的两两交换，相同元素前后的顺序没有变化，冒泡排序是一种稳定的算法
 
5.应用
 
有一个题（我忘了找不到了，描述一下），给你一组数据，要求排成上升序列，每次可以换两个元素的位置，求交换的次数。
 这是典型的应用：求逆序数，所谓逆序数，举个例子，若规定上升序列为正序，则以下序列：3 ，5 ，1 ，4，其中的逆序数有{3，1}{5，1}{5，4}，冒泡排序没交换一次，就消除了一对逆序数，所以： 冒泡排序交换次数为此数列逆序数对数
 2.随意输入两个数字，将这两个数字转为最小后相加
 例如：54321 16249
 输出：12345+12469=24814
 想法1：输入两个数据存入两个int，把数字存到数组中，然后排序（好像随便一个排序方法都行，那么为什么要放在这个地方呢？因为我暂时没想到别的题）,最后输出就得。
 想法2：可以考虑用bool数组来存出现过的数字

 
对于排序算法，相信你一定不陌生吧！如我们常见的几大经典排序：
 
冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等等。
 

 
这些排序算法中，性能、内存消耗各有优劣，同时也各有各的适用场景，而我们也不能仅仅从时间复杂度和空间复杂度的优劣去评断一个排序算法的好与坏，比如冒泡排序和插入排序，两者的时间复杂度均是O(n²)，空间复杂度也都是O(1)，但是插入排序却更常用，而且在很多实际场景中，执行效率更高，至于原因，你可以思考一下，此文暂不做讨论。
 

 
而排序算法中，除了时间复杂度和空间复杂度，还有着一个我们比较常关注的性质：稳定性。
 
我们这里简单描述一下什么是排序算法的稳定性：
 
 
 
对于某一种排序算法，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序保持不变，那么就说这个排序算法是稳定的。
 
 
而上面所提到的几种排序算法中，冒泡排序、插入排序、归并排序属于稳定排序，选择排序、快速排序、堆排序属于不稳定排序。
 

 
简单举个例子：
 
假设对数组[3, 2, 2, 5, 1, 4]进行递增排序，数组中有两个元素是相等的即2，为方便标识，我们先用2'表示第二个2，即原数组为：[3, 2, 2', 5, 1, 4]。
 
 
如果使用稳定排序，那么排序后有且仅有一种结果：[1, 2, 2', 3, 4, 5]。
 
 
如果使用不稳定排序，那么排序后，可能会出现这种结果：[1, 2', 2, 3, 4, 5]
 
 

 
排序的稳定性很好去理解，也很容易去分析。但是你有没有想过：
 
 
 
既然所有的排序算法排出来的结果都是有序的，为什么还要区分稳定性和不稳定性的算法呢？
 
 


 
我们用下面一个场景来说明。
 

 
假设有一万条订单记录，要对这些订单进行一个排序，要求按照金额有小到大的顺序排列，如果订单金额相同，则按照下单时间的先后进行排列。
 
假设订单数据为：
 
 
在开始进行排序时，有一点先要弄明白：像这种存在需要对多个关键字进行排序的，每一次排序只能基于其中某一个且仅一个关键字进行排序，无法对多个关键字同时排序。之所以提这一点，是为了避免有人拿Java的比较器Comparator做对比，那根本是两码事。
 
而对于需要针对多个关键字排序的情况，优先级最高的要放在最后排才行，比如这里先按照金额大小排序，在金额大小相同的情况下，再按照下单时间排序，优先级最高的就是金额，那么就应该最后再排金额。如果先排金额，在排序后，如果有金额相同的，再排下单时间，那么最后的结果就是以下单时间的先后为准了，你好好想一想，是不是这么回事？
 
好，那我们进行排序，先对下单时间进行排序，得到的结果为：
 
 
得到这个结果后，我们再对金额进行一次排序就OK了，但是这里为了达到需求要求的效果，即金额相同的，下单时间早的要排在前面，则第二次排序只能用稳定排序。如果使用不稳定排序，第二次按照金额排序后，得到的结果虽然在金额上是有序的，但下单时间上就不一定有序了，换一种说法就是：第一次按照订单时间排序的结果，没有被第二次按照金额排序利用上，先看图：
 
使用稳定排序后的结果：
 
 
这样子你应该明白了吧，如果使用不稳定排序，那么第二次排序后的结果，就可能不符合要求，不稳定排序会改变相同元素的原有顺序。在这个场景中，不稳定排序就可能会把金额均是30的原有顺序改变了（注意哦，这个顺序是已经按照下单时间排好序的结果），从而导致最终的排序结果对于金额相同的，没有按照时间先后来排序。但是这种问题，使用稳定排序就不会出现。
 

 
所以，现在你明白了吧，之所以区分排序的稳定性和不稳定性，是有它的实际应用场景的，它的意义在于：
 
 
 
在需要对多个（也意味着多次）具有优先级的关键字进行排序的场景下，稳定排序能利用上一次排序的结果服务于本次排序，从而保证对于值相同的元素的两次排序结果相同。
 
 

 
用这个场景来解释就是：
 
第一次排序先对下单时间进行排序，得到的排序结果中，两个金额为30的记录在下单时间上已经是有序的了；然后第二次排序对金额进行排序，由于使用了稳定排序，两个金额为30的记录的顺序就不会被改变了，这就相当于第一次排序的结果被第二次排序利用上了。
 


 
如果你还是不能够完全理解，再举一个实际场景：
 

 
对考生的成绩进行排名，如果总分相同的，则按照语文分数高低排，如果语文分数还相同的，继续按照数学分数高低排。
 
看到这个例子，你是否恍然大悟了呢？
 
在这个例子中，排序的优先级是：总分 > 语文 > 数学，如果使用稳定排序，我们就能得到预期且是正确的结果；如果使用不稳定排序，就有可能会出现，对于总分相同的，语文分数较低的就排在了更前面，这个结果对于成绩排名，就不是正确的。
 

 
这就是稳定排序的实际应用场景，对于某些场景，不稳定排序得到结果可能是不正确的。
 
 
THE END