常用排序算法

 

1到4为比较排序，比较排序的时间下届为N*lgN，所以堆排序和归并排序是渐进最优的比较排序算法。而快速排序则是排序大数组的最常用算法。

1、         插入排序：每插入一个元素，就需要和已排序的数据进行比较，并且移动相关数据。所以效率较低，时间复杂度为O(n^2)。

2、         归并排序：分解待排序的N个元素序列成各具N/2个元素的两个子序列；使用归并排序递归的排序两个子序列；合并两个已排序的子序列以产生排序的答案。时间复杂度为 N*lgN。很多时候我们需要分而治之的思想来解决问题：将问题分解为几个规模更小的问题，各自解决这些小问题，最后合并得到答案。在求解小问题的过程中，我们递归的使用这种思想。

3、         堆排序：堆排序分为两步，建堆和排序， 时间复杂度也是N*lgN。

堆是一颗完全二叉树。

小根堆：父结点小于等于子结点。

大根堆：父结点大于等于子结点。

下面的操作以大根堆为例，小根堆类似。

维护堆操作：将一个结点调整到合适的位置来维护堆的性质，时间复杂度为 lg2n。

建堆：将一组无序数据构造成堆。从底向上对每个元素执行（维护堆操作），简单估算时间复杂度为nlg2n，但是严格的证明结果是，该复杂度为n，线性时间。

堆排序：时间复杂度为 nlg2n。

新增结点，删除结点：都是调整该结点到合适的位置，即维护堆操作。时间复杂度为 lg2n。

取最大值：第一个元素就是，所以时间复杂度为O(1)。非常适合做优先队列。

4、         快速排序：随机选择一个数字，比它小的放前面，比它大的放后面，这样前半部分一定小于后半部分。每个部分递归调用快速排序。期望时间复杂度为N*lgN，最坏时间复杂度是O(n^2)。实际应用中通常比堆排序快。

5到7为线性时间排序：

5、计数排序：每个数都在一个小区间（0 ,K）之间。对每一个输入元素X，确定小于X的元素个数，利用这一信息，就可以直接把X放到数组的合适位置上面了。

6、      基数排序：对数字的每一位进行计数排序。时间复杂度是（位数*N）。虽然基数排序是线性时间复杂度，但是并不一定比快速排序快。这和底层硬件（缓存命中）、输入数据的特征、内存等很多因素相关。

7、      桶排序：适用于数据独立，均匀的在某个区间内分布。将每个数据映射到桶上，映射位置相同则用链表，然后每个链表独立排序即可。

中位数算法：求一个数组中中间大小的数字，或者第i小的数字。

A、      这个算法的思想和快速排序的思想有点相似，随机选择一个数字，将小的放它前面，大的放它后面。一遍过后重新计算i的数值，然后只需要在其中一半里面继续查找，另外一半就补需要关心了。最坏的时间复杂度是O(n^2)，期望为O(n)。

B、      为了保证最坏时间复杂度为O(n)，需要精心选择每次比较的数字。将数组按5个一组进行分配，找出每组的中位数。然后重复这个过程，直到找出这个用来分割的数字，然后用这个数字进行A操作。