算法之排序（上）

排序算法有很多种，甚至有很多都完全没有听过，我们最常见，也最经典的就是：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

按照时间复杂度来进行划分可以将其划分为三类

•O(n2) ：冒泡、插入、选择；基于比较•O(nlogn)：快排、归并；基于比较•O(n)：桶、计数、基数；不基于比较

这次我们来说时间复杂度为O(n2)的

在说具体的排序方法之前，先明确排序算法的评价标准

首先是排序算法的执行效率，执行效率一般从最好、最坏、平均时间复杂度上分析，其分析时间复杂度时需要考虑系数、常数和低阶，因为时间复杂度是在数据规模特别大的时候的增长趋势，在平时的代码中，数量级都是比较小的，所以还需要考虑这些问题。在基于比较的排序算法中，数值比较的次数和数据的移动次数也都是需要考虑进去的。

其次是内存的消耗，算法的内存消耗可以用空间复杂度来表示，当空间复杂度为O(1)的算法也可以称之为原地排序算法。

最后是算法的稳定性，当一组数据中有两个相同的值时，排序之后两个值的顺序是如果没有交换那它就是具有稳定性的算法。

然后我们再引入两个概念，有序度和逆序度

有序度是数组中具有有序关系的元素对的个数。

比如说2、4、3、1、5、6这组数组的有序度是11，因为它有11个有序元素对，分别是(2,4)、(2,3)、(2,5) (2,6)、(4,5)、(4,6)、(3,5)、(3,6)、(1,5)、(1,6)、(5,6)。

对于6、5、4、3、2、1这组数据，它的有序度是0；对于1、2、3、4、5、6这组数据来说，它的有序度是n*(n-1)/2，这种完全有序的数组的有序度叫做满有序度。

所以逆序度也就等于满有序度-有序度，排序的过程就是增加有序度，减少逆序度的过程，最后到达满有序度，排序就结束了。

冒泡排序是依次对两个相邻的值进行比较，如果满足要求的大小关系，就继续往后看，如果不满足就将它们两个互换位置。每一次冒泡都最起码会交换一个值 ，所以最多执行n次就可以完成排序操作。

如果一组数据为4、5、6、3、2、1，要求其从小到大排序，那它进行第一次冒泡排序的过程就是这样的

这个时候，最大的数字6，就已经排在了正确的位置上，后续的冒泡操作依次是这样的

这种情况是刚好用了n次，如果代码直接写成循环n次的话，就可能会有多余的判断流程，如果排列顺序刚好为1、2、3、4、6、5的话，就只需要一次就可以完成排序操作，所以我们可以将每次有无数据交换的操作来作为有无完成排序的条件。

首先冒泡排序只交换相邻两个数据，所以空间复杂度为O(1)，是原地排序算法。

在冒泡排序中，我们可以规定它在两个数值相等的时候不进行交换，就可以保证排序前后相同的数值先后顺序不变，所以它是一个稳定的排序算法。

在数组中，我们在中间插入一个数据的时候，是把相应位置的数据都往后挪一位，同时还可以保证顺序不变，同样的方法放到算法中，就有了插入排序。

首先是将数据分为两个区间，已排序区间和未排序区间，开始的时候，已排序区间只有一个元素，然后在未排序区间中取一个元素，在已排序区间中寻找对应的位置将其插入，不断重复直到未排序区间的数据为空。

比如要将4、5、6、1、3、2这组数据进行排序，那过程就是这样的

插入排序与冒泡排序一样，有比较和移动两个操作，循环比较得到要插入的位置，然后将后面的元素往后挪一位。

对于不同的查找插入点方法，不管是从头到尾，还是从尾到头，元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。

还是拿刚刚的例子说，满有序度是n*(n-1)/2=15，初始序列的有序度是5，所以逆序度是10。

在插入排序的时候，我们并不需要额外的空间，所以空间复杂度是O(1)，所以它是一个原地排序算法。

因为在插入的时候，我们可以让未排序区间的元素排在已排序区间中相同元素的后面，所以它也是一个稳定的排序算法。

选择排序和插入排序比较类似，也有已排序区间和未排序区间，但是初始的时候是不对其进行区分的，选择排序每次都会在未排序区间中选择最小的一个数，将它放到已排序区间的末尾，如果没有已排序区间就将其放到未排序区间的前面。

首先选择排序也不需要申请多余的内存空间，空间复杂度为O(1)，是原地排序算法。

由于它将数值与前面的数值进行交换，这样将会破坏它的稳定性，所以它是一个不稳定的排序算法。

相比之下，选择排序比冒泡排序和插入排序稍微逊色一点，拿冒泡排序和插入排序相比呢，从代码上看的话，冒泡排序进行数据交换是需要有第三个变量来做交换的，有三个赋值语句，而插入排序只需要一个赋值语句即可完成赋值操作，所以插入排序比冒泡排序性能更好一点。

参考文档

极客时间-数据结构与算法之美