校招面试中，经常会问到排序算法。排序算法很多，容易忘记和混淆。建议保存下来，面试前快速过一遍。俗话说：战前磨枪，不快自乐。冒泡排序反复遍历待排序数组，一次比较两个数，顺序不对就交换。因为在交换过程中，较小的数会慢慢“浮”到数组的顶端，所以称为冒泡排序。具体过程如下：比较相邻的数，如果第一个数大于第二个数，则进行交换。对每一对相邻的数做同样的事情，从开头的第一对到末尾的最后一对，这样末尾的数就是最大的数。对所有数字重复上述步骤，除了最后一个数字（因为最后一个数字已经是最大的）。对越来越少的数字重复上述步骤，直到整个数组排序完毕。快速排序是通过一次排序将待排序数组分成两个子数组。一个子数组的个数小于另一个子数组的个数，可以将两部分分别排序，最后对整个数组进行排序。具体过程如下：选择一个参考数，通常是数组中的第一个数。重新排列数组，使所有小于参考数字的数字都放在参考数字的前面，所有大于参考数字的数字都移到参考数字的后面。排序后，引用编号位于已排序数组的正确位置。继续按照上述步骤对引用号前后的两个子数组进行排序，直到整个数组有序为止。插入排序在待排序的数组中，将第一个位置的数字视为一个有序的子数组，然后从第二个数字开始逐个插入，直到整个数组有序。希尔排序希尔排序是插入排序的升级版。首先将整个数组分成若干个子数组进行插入排序。当整个数组中的数字基本有序时，再对整个数组进行插入排序。具体过程如下：选择一个增量序列t1，t2，...，tk，其中ti>tj，tk=1。例如：40,13,4,1。根据增量序列号k，序列被插入并排序k次。对于每一次插入排序，将数组按照对应的增量ti分成若干个子序列，对每个子数组分别进行插入排序。当最后一个增量为1时，对整个数组进行插入排序。选择排序在待排序数组中，先找到最小的数，与第一个位置的数交换；然后在剩余的数中找出最小的数，与第二位的数交换；以此类推，直到将倒数第二个数与最后一个数进行比较。堆排序堆排序是利用堆的数据结构设计的一种排序算法。堆排序可以分为两个阶段：堆构建阶段和下沉排序阶段。在堆构建阶段，我们将原来的数组重组为堆；然后在下沉排序阶段，我们按降序从堆中取出所有元素，得到排序后的结果。归并排序将两个有序数组合并为一个有序数组。也就是把待排序的数组分成两个子数组，当每个子数组都排好序后，再把两个子数组合并成整个数组，也叫双向归并排序。如果将待排序的数组分成多个子数组，则称为多路归并排序。计数排序计数排序使用了一个额外的数组，其中第i个数是待排序数组中等于i的数。然后根据这个追加的数组，把数组中需要排序的数排到正确的位置。桶排序桶排序就是把待排序的数组分成有限个桶，然后用桶排序或者其他排序算法对每个桶分别进行排序。基数排序基数排序就是把整数按照位数分成不同的数，然后分别比较每一位。先按低位排序，再收集；然后按照高位排序，然后收集；依此类推，直到最高阶。排序算法总结复杂度总结排序算法时间复杂度（平均）时间复杂度（最差）时间复杂度（最佳）空间复杂度稳定性冒泡排序O(n2)O(n2)O(n)O(1)√快速排序O(nlogn)O(n2)O(nlogn)O(logn)×插入排序O(n2)O(n2)O(n)O(1)√希尔排序O(nlogn)O(n2)O(n)O(1)×选择排序O(n2)O(n2)O(n2)O(1)×堆排序O(nlogn)O(nlogn)O(nlogn)O(1)×归并排序O(nlogn)O(nlogn)O(nlogn)O(n)√计数排序O(n+k)O(n+k)O(n+k)O(n+k)√桶排序O(n+k)O(n+k)O(n2)O(n+k)√基数排序O(n*k)O(n*k)O(n*k)O(n+k)√
