数据结构：排序

1.排序的概念及其运用

2.常见排序算法的实现

（1）

插入排序法： 时间复杂度为O（N）~O（N^2）

希尔排序法： 结论 时间复杂度为O（N^1.3）

与gap有关 N*logN （底数就是gap）----这个是可以近似看为

 因为外面一层为logN  经过预排序后 里面的循环分两端（gap 很大  和gap很小）但都是N

1：预排序 ---目的是为了使数组接近有序  ————分组排序

比如间隔为3 的分为一组   一共分了三次  （能使大的更快的跳到后面）

这里gap就是间隔  那gap多少合适呢

gap越大，跳的越快，越不接近有序

gap越小，跳的越慢，越接近有序

gap要根据数据个数来决定

2：直接插入 也就是gap为1 的时候

（2）

直接选择排序

时间复杂度在任何情况下都为O（N^2）

冒泡排序和插入排序  表面上时间复杂度情况相同  但是根据具体情况

有序：一样

接近有序：有一些差距

部分有序：差距就很大

快速排序:

1. hoare版本

选出一个基准值 key 把他放到正确的位置（最终排好序要蹲的位置）

左边作key  右边先走 ，保证相遇位置的值比key小

原因：因为相遇的时候一定时左边L向右走导致与R相遇（这时候R一定是找到了比key大 或者R一直走到L的位置）

右边作key 左边先走， 保证相遇位置比key大

原因： 因为相遇的时候一定是右边R向左走导致与L相遇  （这时候L一定找到了比key大 或者是L一直走到R的位置）

2 挖坑法

3 前后指针法

cur找到比key 小的值 pre++  cur和prev位置交换  cur++;

cur找到比key大的值 ，cur++

说明 ： prev要么紧跟着cur prev下一个就是cur

            prev跟cur之间有着一段比key大的序列

（总体上相当于把大的数据向后推）

递归太深就会导致栈溢出

递归改非递归

三路划分：能够解决快速排序面对大量重复数据

1 直接改循环  （斐波那契数列）

2 使用栈辅助改循环

两个有序区间归并的思路：依次比较，小的尾插到新空间（思路和后序遍历差不多） 

时间复杂度为O（N*logN）

归并排序同时可以运用到磁盘排序（不需要随机访问）

3.排序算法复杂度及稳定性分析

稳定性是指相同数据相对位置是否稳定