排序

总结

选泡快插基 统计堆归希

1.基于比较的排序

1）简单排序（熟练掌握插排）

1、选择排序

人的排序思想；每次选出最大（最小），不稳，特慢。

优化：每次同时选出最大和最小，放在头和尾。

最好、最坏、平均时间复杂度均为N**2

2、冒泡排序

类似鱼吐泡泡；相邻比较交换，每次将最大(或最小)换到正确位置，稳定，特慢

优化：第一次遍历完数组，没有发生交换直接返回。

最好时间复杂度为N，最坏、平均时间复杂度为N**2

3、插入排序

类似扑克插牌；每次将一个数插入到已排好序的数组中。稳定、较快。数组越有序，插入排序越快。当数据量小于60时，一般默认用插排。

优化1：通过二分查找直接找到要插入的位置，执行数组插入的过程。

优化2：在二分查找的前提下，一次找两个待插入数的位置，执行数组插入的过程

最好时间复杂度为N，最坏、平均时间复杂度为N**2

2）复杂排序

1、希尔排序

希尔排序也是对插入排序的优化，但是失去了稳定性。它将每次插入的间隔变大了，跳着插入。因为跳着插，所以不稳。

方法：将普通插入排序的内层循环改成间隔为gap的插入，外层循环不变。在最外层套上一层控制gap变化的循环。

方法一：希尔版gap=a.length/2;gap>0;gap=/2

方法二：Knuth序列：k=1;k=3*k+1

最好时间复杂度：N；平均时间复杂度：N**1.3； 最坏时间复杂度：N平方

2、归并排序

通过分治思想，将对一个数组排序分解成：将一个数组均分成两个子数组，将子数组排好序后再合并成一个数组（merge）。子数组的排序可以递归调用该过程。

所以，归并排序有一个分和合的过程；且会递归调用函数，直至子数组只剩1个数

优化：当数组规模较小时，使用插排。

最好、最坏、平均时间复杂度均为N**2；稳定。

3、快速排序

通过分治思想，将对一个数组排序分解成：取数组中一个数，将大于它的放它右边，小于等于的放左边。将数组分成了两个区：小于等于区、大于区。对两个区再递归调用排序过程。每次排序过程 排好了一个数，且将数组分成两个区。

所以，快速排序有个partition（分）的过程；且会递归调用排序函数，直至子数组只剩1个数。

优化1：每次partition（分）的过程将数组分成三个区，小于区，大于区，等于区。等于区的已排好序，将等于区的起始下标和中止下标记录。将小于区和大于区重新递归调用函数。因为每次排好了一个或多个数，需要空间记录，所以空间复杂度为logN。

优化2 ：随机快排。因为普通快排是取数组的固定位置：尾或头，所以跟数据样本情况有关，最坏时间复杂度会达到N**2（即：已有序时退化成选择排序）。于是改为随机取值，成功消除掉最坏情况，最坏时间复杂度数学统计为NlogN.

优化3：双轴快排。从单边比较优化成为双边比较，当遇到不符合时停下，当另一边也不符合时，交换。

平均、最好时间复杂度：NlogN；普通快排最坏为N**2,随机快排最坏为NlogN

4、堆排序

堆是特殊的完全二叉树，大顶堆是每一个子树的根结点都为最大值的堆。

优先级队列就是用堆实现的。堆一般由数组存储，heapSize表示堆大小。

index为当前元素数组下标，parent为父节点，left为左节点,right为右节点。

left=index*2+1 right=left+1 parent=(index-1)/2

堆的新增heapInsert时间复杂度为logN,堆的构建是将一个个数插入，为O(N)

堆的调整heapIfy时间复杂度为logN,当index上的元素变小时，只需下沉

下沉操作中与子节点比较大小，当比所有子节点大或没有子节点时停止下沉

堆排序过程：

先构建一个大顶堆，然后将根节点与最后一个叶子节点交换，同时heapSize-1(删去堆根节点的同时将最大数排在了数组末尾)；对堆顶元素做heapIfy操作；调整完后再重复删去根节点过程，直至heapSize为0或1.

最好、最坏、平均时间复杂度：NlogN ；不稳定（跳着换的，只跟子父比较交换）

2.桶思想的排序（稳定）

1.桶排序

2.基数排序

3.计数排序