排序算法非常多，这里我们只学习众多排序算法中最经典、最常用的一小部分：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

    1如何分析一个“排序算法”？       

    （1）排序算法的执行效率

        对于排序算法执行效率的分析，我们一般会从这几个方面来衡量：

        1.最好情况、最坏情况、平均情况时间复杂度

        对于要排序的数据，有的接近有序，有的完全无序，有序度不同的数据，对于排序的执行时间肯定是有影响的，我么要知道排序算法在不同数据下的性能表现。

        2.时间复杂度的系数、常数、低阶

        在实际的软件开发中，我们排序的可能是规模很小的数据，所以在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

        3.比较次数和交换（或移动）次数

    （2）排序算法的内存消耗

        排序算法的内存消耗也可以通过空间复杂度来衡量，不过针对排序算法的空间复杂度，我们引入了一个新的概念：原地排序。原地排序算法，就是特指空间复杂度是O(1)的排序算法。

    （3）排序算法的稳定性

        针对排序算法，我们还有一个重要的度量指标：稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。   

        比如，有一组数据：5,7,2,1,5,8，按大小排序后为：1,2,5,5,7,8。这组数据里面有两个5，经过某种排序算法排序之后，如果两个5的前后顺序没有改变，那我们就把这种排序算法叫做稳定的排序算法，如果前后顺序发生变化，那对应的排序算法就叫做不稳定的排序算法。

    2冒泡排序

        冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。依次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

        下面用一个例子来看看冒泡排序的整个过程。对一组数据：4,5,6,3,2,1，从小到大进行排序，第一次冒泡操作的详细过程如下：

        经过依次冒泡操作之后，6这个元素已经存储在正确的位置上了。要想完成所有数据的排序，我们只要进行6次这样的冒泡操作就行了。

        如下图所示：

        刚刚冒泡的过程还可以优化：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

        下面的例子给6个元素排序，只需要4次冒泡操作就可以了：

        冒泡排序的代码：

        运行结果：

        总结三点：

        第一，冒泡排序是原地排序算法。因为冒泡的过程指设计相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是原地排序算法。

        第二，冒泡排序是稳定的排序算法。在冒泡排序中，只有交换才可以改变两个元素的前后顺序，为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

        第三，冒泡排序的最好情况时间复杂度是O(n)，最坏情况时间复杂度是O(n^2)，平均情况时间复杂度是O(n^2)。要排序的数据已经是有序的是最好的情况，我们只需要进行一次冒泡操作。要排序的数据刚好是倒序排列的是最坏的情况，我们需要进行n次冒泡操作。

        这里来说一下平均时间复杂度的推导方法，这个方法其实并不严格，但是比较实用。我们引入有序度的概念，有序度就是有序的元素对的个数：

        比如：

        对于一个倒序排列的数组，有序度是0；对于一个完全有序的数组，有序度就是n*(n-1)/2，我们把这种完全有序的数组的有序度叫做满有序度。

        逆序度的定义跟有序度正好相反：

        这三个概念间还存在一个公式：逆序度=满有序度-有序度。

        我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

        冒泡排序包含两个操作原子：比较和交换。每交换依次，有序度就加1，而交换的次数总是确定的，即为逆序度，也就是n*(n-1)/2-初始有序度。

        而最坏情况下的交换次数是n*(n-1)/2，最好情况下的交换次数是0，我们取个中间值，即为n*(n-1)/4。比较操作肯定比交换操作多，而复杂度的上限是O(n^2)，所以平均情况下的时间复杂度就是O(n^2)。

    3插入排序

        我们先来看看插入排序的思想。

        一个有序的数组，我们往里面添加一个新的数据，为了保持有序，我们需要遍历数组，找到数据应该插入的位置再将它插入：

        我们把这个思想用到排序中，需要将数组中的数据分为两个区间：已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将它插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

        一个例子：

        插入排序包含两个操作：元素的比较和元素的移动，通过比较找到插入位置，然后将插入点后的元素顺序往后移动一位，腾出位置给元素插入。

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

        下图中例子的满有序度为n*(n-1)/2=15，初始序列的有序度是5，逆序度是10，移动次数为3+3+4=10：

        插入排序的代码（写的过程中捋了好几次才捋顺，以后再写几遍！）：

        运行结果：

        总结一下：

        第一，插入排序是原地排序算法。它并不需要额外的存储空间，空间复杂度是O(1)。

        第二，插入排序是稳定的排序算法。对于值相同的元素，我们选择将后面出现的元素插入到前面出现元素的后面，这样就保持了原有的前后顺序不变。

        第三，插入排序的最好时间复杂度为O(n)，最坏时间复杂度是O(n^2)，平均时间复杂度是O(n^2)。

    4选择排序

        选择排序的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

        选择排序原理示意图：

        直接简单总结一下：

        第一，选择排序空间复杂度为O(1)，是原地排序算法。

        第二，选择排序的最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度都是O(n^2)。

        第三，选择排序是不稳定的排序算法。由上面图示的过程可以看出，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。比如5,8,5,2,9这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5的顺序就变了，所以就不稳定了。

    5为什么插入排序比冒泡排序更受欢迎呢？

        选择排序是不稳定的排序算法，所以比冒泡排序和插入排序要逊色。

        插入排序和冒泡排序的时间复杂度都是O(n^2)，都是原地排序算法，而且都是稳定的排序算法。那么为什么插入排序比冒泡排序更受欢迎呢？

        前面有讲到，冒泡排序和插入排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个，如下图所示：

        若执行一个赋值语句的时间粗略的估计为单位时间，分别用冒泡排序和插入排序对同一个逆序度是K的数组进行排序，用冒泡排序需要K次交换操作，每次需要3个赋值语句，交换操作总耗时就是3*K个单位时间，而插入排序中数据移动操作只需要K个单位时间。

        因此，虽然他们的时间复杂度是一样的，但是如果我们希望把优化做到极致，肯定首选插入排序。插入排序也可以进行优化，感兴趣的话可以学习一下希尔排序。

    6小结

        要想分析、评价一个排序算法，需要从执行效率、内存消耗、稳定性三个方面来看。

        这三种时间复杂度为O(n^2)的排序算法中，冒泡排序、选择排序我们更多的是了解它的理论，实际开发中应用并不多，插入排序还是挺有用的，有些编程语言中的排序函数的实现原理会用到插入排序算法（优化后的）。

        这三种排序算法对于小规模数据的排序非常高效，但是大规模数据排序的时候，时间复杂度还是稍微有点高，下一节我们会讲更适用于大规模数据的时间复杂度为O(nlogn)的排序算法~

        戳这里查看源代码。