常见排序算法可以分为两大类：

1、非线性时间比较类排序

通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

2、线性时间非比较类排序

不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

各排序算法复杂度及稳定性：

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

稳定性算法:   基数排序 , 直接插入排序 , 冒泡排序, 归并排序

不稳定性算法:   桶排序,    二分插入排序,希尔排序, 快速排序,   简单选择排序,堆排序

各种算法稳定性详解

(1)基数排序(稳定)与桶排序(不稳定)

这两种算法都是属于分配排序算法.(利用元素值本身的信息直接映射到一个辅助序列中变成有序的.而不是通过与其他元素比较确定顺序位置)

基数排序因为在是把低位按顺序映射到一个临时序列中去,是依次序映射,没有涉及到数据位置的变动.然后再按高位顺序映射.所以相同元素也是按次序映射过去.所以是稳定的

如果数据元素没有重复的则采用简单桶排序,此时没有重复元素,所以自然不存在稳不稳定这一说.如果有重复元素得用改进的桶排序.此时辅助的临时数组只是通过索引来识别待排序元素的键值.丢失了其他信息(这是所有采用辅助的临时序列的算法中唯一一个会丢失信息的算法).假如待排序元素是一个map类型,按它的键值来排序.其他算法采用辅助序列时是把map类型做为元素去考虑的.而只有改进的桶排序不会把map类型当元素,只是利用到了键值信息. 这样一来就无法区分键值相同的信息,因此自然是不稳定的算法了啊.

(2)归并排序(稳定)

归并排序使得了递归的思想,把序列递归的分割成小序列,然后合并排好序的子序列.当有序列的左右两子序列合并的时候一般是先遍历左序列,所在左右序列如果有相等元素,则处在左边的仍然在前,这就稳定了.但是如果你非得先遍历右边序列则算法变成不稳定的了.虽然这样排出来的序也是对的,但变成了不稳定的,所以是不太好的实现.

(3)简单选择排序(不稳定)与堆排序(不稳定)

这两种算法都属于选择排序.(从待排序的元素中挑选出最大或最小值.下面的例子以最小值为例)

简单选择排序由于选出最小值后需要交换位置,位置一变就会变得不稳定.例如8  3  8  1.当从左往右遍历找最小值时,找到了1,这就需要把8跟1交换.这样两个相等元素8的位置就变了.

堆排序的话,也会存在跟上面一样的交换最大值的位置会导致不稳定.例如有大堆 8 8 6 5 2.先选出第一个最大值8,放最末尾.此时就不稳定了.因为第二个8就跑它前面去了.

(4)冒泡排序(稳定)与快速排序(不稳定)

这两种算法都属于交换排序.

冒泡是通过不停的遍历,以升序为例,如果相邻元素中左边的大于右边的则交换.碰到相等的时就不交换保持原位.所以是稳定的.当然如果你非得吃饱了撑着了,在碰到相等的时也交换下,那肯定变成不稳定的算法了.

快速排序是不稳定的.举例8   5   6  6 .以8为基准,第一趟交换后最后一个6跑到第一位,8到最后.第二趟交换.这个6跑到5的位置.变成有序的了.两个6位置变了,所以是不稳定的.

(5)直接插入(稳定),二分插入排序(不稳定)与希尔排序(不稳定)

直接插入时是先在已排序好的的子序列中找到合适的位置再插入.假设左边是已排序的,右边是没排序的.通过从后向前遍历已排序序列,然后插入,此时相等元素依然可以保持原有位置.但是如果你从前向后遍历已排序序列就会是不稳定排序了.

二分插入排序是不稳定的,因为通过二分查找时得到的位置不稳定.例如3 4 4 5 4.但把最后一个4插入时肯定会跑到第二个4前面去了.所以是不稳定的.

时间复杂度：

1. 时间复杂度

O(1)  O(n)  O(m+n)  O(logn)  O(nlogn)   O(n²)

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

记作T(n)=Ｏ(f(n))，称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

上面这一段解释是很规范的，但是对于非专业性的我们来说并不是那么好理解，说白了时间复杂度就是时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。通常我们计算时间复杂度都是计算最坏情况 。

最坏时间复杂度和平均时间复杂度

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。设每种情况的出现的概率为pi，平均时间复杂度则为sum(pi*f(n))

空间复杂度：

一个程序的空间复杂度是指运行完一个程序所需内存的大小。

利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。

一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。　　

（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。

（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。

一个算法所需的存储空间用f(n)表示。

S(n)=O(f(n))　　其中n为问题的规模，S(n)表示空间复杂度。 

稳定性：

所谓稳定性是指待排序的序列中有两元素相等，排序之后它们的先后顺序不变.

假如为A1，A2.它们的索引分别为1，2.则排序之后A1，A2的索引仍然是1和2.

稳定也可以理解为一切皆在掌握中，元素的位置处在你在控制中.

而不稳定算法有时就有点碰运气，随机的成分.

当两元素相等时它们的位置在排序后可能仍然相同，但也可能不同，是未可知的.

另外要注意的是：

算法思想的本身是独立于编程语言的，所以你写代码去实现算法的时候很多细节可以做不同的处理.采用不稳定算法不管你具体实现时怎么写代码，最终相同元素位置总是不确定的(可能位置没变也可能变了).而稳定排序算法是你在具体实现时如果细节方面处理的好就会是稳定的，但有些细节没处理得到的结果仍然是不稳定的.

比如冒泡排序，直接插入排序，归并排序，虽然是稳定排序算法，但如果你实现时细节没处理好得出的结果也是不稳定的.

稳定性的用处

我们平时自己在使用排序算法时用的测试数据就是简单的一些数值本身，没有任何关联信息，这在实际应用中一般没太多用处.

实际应该中肯定是排序的数值关联到了其他信息，比如数据库中一个表的主键排序，主键是有关联到其他信息，另外比如对英语字母排序，英语字母的数值关联到了字母这个有意义的信息.

可能大部分时候我们不用考虑算法的稳定性，两个元素相等位置是前是后不重要，

但有些时候稳定性确实有用处，它体现了程序的健壮性.

比如你网站上针对最热门的文章或啥音乐电影之类的进行排名，由于这里排名不会像我们成绩排名会有并列第几名之说，所以出现了元素相等时也会有先后之分，如果添加进新的元素之后又要重新排名了，之前并列名次的最好是依然保持先后顺序才比较好.

面对这以多排序算法你可能排序时用哪种算法好呢? 每种算法适用哪些场景?

为了对比上面各种不同算法,可以从如下几个方面来考虑.

1. 排序算法的稳定性

2. 排序算法时间复杂度

3. 排序算法空间复杂度

4. 各种算法适用的最佳场景.

1.简单选择排序 2.堆排序        (1和2是属于选择排序)

3.直接插入排序 4.希尔排序     (3和4属于插入排序,有时把改进后的直接插入排序叫做二分插入)

5.冒泡排序         6.快速排序     (5和6属于交换排序.交换排序顾名思义是不停的交换数据位置.但实际上选择排序也在不停的交换元素,但次数较少,只有找到最大值才一次交换.侧重点还是在通过遍历或堆来选择出最值.而冒泡排序就是通过不停交换相邻元素得出最大值,快速排序也在不停交换元素使序列一步步接近有序.侧重在交换)

7.基数排序       8.桶排序         (7和8属于分配排序)

9.归并排序

1、稳定性

归并排序、冒泡排序、插入排序。基数排序是稳定的

选择排序、快速排序、希尔排序、堆排序是不稳定的

2、时间复杂度

最基础的四个算法：冒泡、选择、插入、快排中，快排的时间复杂度最小O(n*log2n)，其他都是O（n2）

3.排序算法的思想：

(1)冒泡排序：

是相邻元素之间的比较和交换，两重循环O(n2)；所以，如果两个相邻元素相等，是不会交换的。所以它是一种稳定的排序方法

(2)选择排序：

每个元素都与第一个元素相比，产生交换，两重循环O(n2)；举个栗子，5 8 5 2 9，第一遍之后，2会与5交换，那么原序列中两个5的顺序就被破坏了。所以不是稳定的排序算法

(3)插入排序：

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。刚开始这个小序列只包含第一个元素，事件复杂度O(n2)。比较是从这个小序列的末尾开始的。想要插入的元素和小序列的最大者开始比起，如果比它大则直接插在其后面，否则一直往前找它该插入的位置。如果遇见了一个和插入元素相等的，则把插入元素放在这个相等元素的后面。所以相等元素间的顺序没有改变，是稳定的。

(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个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法

总结

1.只要不涉及到两个元素之间位置的交换就肯定是稳定的排序算法.比如归并排序,基数排序.(桶排序不稳定是个特例,因为它丢失了附带信息,不然的话可以弄成稳定排序的)

2.在涉及到不同位置元素交换的算法中除了冒泡和直接插入排序是稳定的,其他都是不稳定的.

你可以这样想,之所以出现相同元素位置变了就是其中一个交换位置时从另一个头顶跳过去了,而冒泡算法是相邻位置互换,跳不过去的,碰到相等元素的时候就停住不交换了.

而直接插入排序是往已排好序的序列中插入.所以你通过由后往前遍历碰到相等的时就停住,这样也能保持稳定.但记住一定得从后往前遍历,不然也会不稳定.(所以说直接插入是半稳吧,而冒泡是非常的稳啊,除非你闲得蛋痛非得把两相等的元素两两交换)

参考：

十大经典排序算法的复杂度分析

数据结构中各种排序算法的稳定性比较

面试十大经典排序算法（动画演示）

冒泡排序：https://blog.csdn.net/alzzw/article/details/97906690

选择排序：https://blog.csdn.net/alzzw/article/details/97964320

插入排序：https://blog.csdn.net/alzzw/article/details/97967278

快速排序：https://blog.csdn.net/alzzw/article/details/97970371

归并排序：https://blog.csdn.net/alzzw/article/details/98047030

堆排序：https://blog.csdn.net/alzzw/article/details/98087519

基数排序：https://blog.csdn.net/alzzw/article/details/98240042

计数排序：https://blog.csdn.net/alzzw/article/details/98245871