数据结构：排序
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.排序算法复杂度及稳定性分析
稳定性是指相同数据相对位置是否稳定