注：

lgN在这里为1og2N简写

为了方便描述,本文默认用int类型比较，从小到大排序

本文排序算法以java语言实现

本文的排序都是比较排序

比较次数和赋值和交换次数有的排序不好分析，可能不准确

一.插入排序

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

从第一个元素开始，该元素认为已经被排序；

取出下一个元素，在已排序的元素序列中从后向前扫描；

如果已排序元素大于新元素，新元素继续比较前一个元素，直到找到已排序的元素小于或者等于新元素的位置；

将新元素插入到该位置后；

重复步骤2~4。

java实现

插入排序为两层循环嵌套，时间复杂度O(N2),插入排序的while循环是先比较，移动待插入的位置，循环结束才真正交换数据位置。这里需要注意，常用的for循环嵌套进行插入排序会每次比较都和前面元素交换直到插入到待插入位置，上面的内循环用while寻找待插入位置，把其他元素后移的算法更合理，每次插入只一次进行一次交换。

因插入排序每次只比较相邻一位数据，对于逆序较多的数组效率低，衍生算法希尔排序，会大幅加快逆序交换，后面详细介绍。

二.选择排序

在未排序序列中找到最小元素，放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾，循环直到所有元素均排序完毕。

初始状态：无序区为R[1..n]，有序区为空；

第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n]。该趟排序从当前无序区中选出最小的记录 R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；

循环n-1次，排序完成。

java实现

选择排序为两层for循环嵌套，内层循环始终去找最小值，放到最前面。交换次数比冒泡排序少很多，所以实际执行效率比冒泡排序快。

衍生算法，双向选择排序（每次循环，同时选出最大值放在末尾，最小值放在前方），可以提高选择效率。

三.冒泡排序

重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换

初始状态：无序区为R[1..n]，有序区为空；

第i趟排序(i=0,1,2…n-1)开始时，当前无序区和有序区分别为R[0..n-i]和R[n-i+1..n]。对每一对相邻元素进行比较，从开始第一对到结尾的最后一对，如果第一个比第二个大，就交换它们两个，这样在最后的元素应该会是最大的数，使R[1..n-i-1]和R[n-i..n]分别变为记录个数减少1个的新无序区和记录个数增加1个的新有序区；

循环n-1次，直到排序完成。

java实现

冒泡排序在代码实现上是最简单的，不需要什么思考，两层for循环嵌套，比大小交换。因为冒泡通常的例子都是让大的往后移，对于刚接触排序的人来说看来上面可能认为冒泡排序与选择排序是反向操作，其实冒泡排序也可以把小数向前移，这样能明显的看出冒泡排序和选择的排序的不同，针对无序区的元素，冒泡排序总是不断地交换，而选择排序是先找出最小的元素再做一次交换。

衍生算法，鸡尾酒排序，该排序从左往右找出最大值后，再从右往左，找出最小值，类似鸡尾酒搅拌左右循环,在某些情况下，优于冒泡排序。

四.希尔排序

插入排序的改进版，优先比较距离远的元素，减少交换次数

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

按增量序列个数k，对序列进行k 趟排序；

每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

java实现

上面是常用的写法，每次比较，如果前面的更大都会交换，可以优化一下,直接把上面插入算法嵌入内循环，比较的间隔由1改为h,比较的时候只移动插入位置，比较完只需交换一次

java实现

希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N1.5)，希尔排序时间复杂度的下界是Nlg2N。希尔排序没有快速排序算法快 O(N(lgN))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(N²)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。

五.堆排序

堆就是完全二叉树，分为最大堆和最小堆，最大堆要求节点的元素都要不小于其孩子（最小堆要求节点元素都不大于其孩子），对左右孩子的大小关系不做要求，所以处于最大堆的根节点的元素一定是这个堆中的最大值。堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依此类推，最终得到排序的序列。

将初始待排序关键字序列(R1,R2….Rn)构造成最大堆，此堆为初始的无序区；

将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

java实现

因为堆的父节点k的子节点为2k和2k+1，下标为0会导致父节点和左子节点都是0，所以上述排序的数组从下标从1开始比较方便。堆排序只需要NlgN的时间，而且算法稳定，只需要少量辅助空间，是最优的利用时间和空间的方法，但因为它的缓存命中率低，应用很少用它，多用于嵌入式。

六.归并排序

递归的把已有序列均分为两个子序列，使子序列有序，合并子序列

把长度为n的输入序列分成两个长度为n/2的子序列；

对这两个子序列分别采用归并排序；

将两个排序好的子序列合并成一个最终的排序序列。

java实现

归并排序是分治法的典型应用，高效稳定，但是归并排序需要一个数组长度的辅助空间，在空间成本高的时候不适合使用。

七.快速排序

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

从数列中挑出一个元素，称为 “基准”（pivot）；

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

java实现

快速排序是通常情况下的最优选择，高效只需要lgN级别的辅助空间，但是快速排序不稳定，受切分点的影响很大

七种排序总结

上面详细介绍了七种排序的实现细节和特点，下面的表格总结了七种排序的各种特征。

其中插入排序，选择排序，冒泡排序都是简单排序，时间复杂度是O(N2),其中插入排序和冒泡排序适合原始序列有序的数组，选择排序的交换和赋值次数会比较少，可以根据不同环境和数据的实际情况和长度选择具体的排序。整体插入排序优于选择排序优于冒泡排序。希尔排序是插入排序的优化，突破了前三个排序O(N2)的时间复杂度，但是本质还是插入排序，突破比较相邻元素的惯性思维，直接比较一定间隔的元素，大幅度减少了逆序调整的比较次数和交换次数，从而达到比较理想的算法复杂度，适合对中等规模数组进行排序。堆排序是利用了最大堆的特点，始终把堆顶元素（最大元素）和最后一个元素替换，再重新构造最大堆，重复执行达到排序的效果。堆结构的特性让算法的复杂度降低到NlgN级别，但是有不方便索引元素的确定，缓存命中率较低。而归并排序则是充分运用了分治原理，把大问题不断的拆分成小问题，进行排序，再合并小数组达到整体排序的目标，归并排序即高效又可靠，唯一的缺点是需要数组长度的辅助空间，在空间成本低的时候适合使用。快速排序则解决了归并排序占用空间的问题，在数组内部用很小的辅助栈，即可完成对元素的分离，再去解决分离后的更小的数组，正常情况下拥有和归并相同级别的时间复杂度，但是得注意选取好切分元素。 实际上一个复杂的序列可能用不止一种排序，例如分治和快速排序在分割到很小的序列时再进行分割反而效率不如插入排序等简单排序，可以设置一定的阈值，先用分治或者快速排序的方式分割数组，再转换成插入等简单排序完成最终的排序。

希望本文能加深大家对排序的理解。我的微信公众号：程序之路，会持续发布技术成长文章，欢迎长按或者扫描二维码关注