快排与归并
# 快排与归并
# 快排
寻找中值的方法有三种 1.单向寻找 2.双向寻找 3.三分寻找 对中值两边的数组递归排序
优化：
- 选取主元的方式优化 每次取数组范围的首位可能使得中值两边的数组长度不均匀，极端情况下可能计算出的中值下标就是首位或末尾，这样就没法做到规模下降一半。所以主元可以取头部尾部中部三个数值中大小位于中间的那个，与首位交换位置后，再计算中值下标
- 当数组规模下降到8个以内的时候，使用插入排序更快一些。 因为插入排序实际规模是n*(n-1)/2,快排的实际规模是nlog(n+1) ,n小于8的时候插入排序快一些。
# 归并
直接用 (left+right)>>2 取中值 递归排序 合并
重点在合并这一步，思路是复制一份数组，然后将左半部分右半部分较小的依次放回原数组
# 例题
将一个数组中的奇数和偶数分开，使得奇数在偶数前面 解题思路： 领取一个数组，遍历原数组，将奇数放到新数组头部，偶数放到新数组尾部。 但是这样会开辟额外的空间。可以考虑直接在原数组上做。 参考快排中双向寻找的思路，左指针从头向尾移动，右指针从尾向头移动，每次将左指针遇到的偶数与右指针遇到的奇数交换。
求乱序数组中第k大的数 解题思路：使用快排对数组排序，然后取第k个，这样的时间复杂度是快排的时间复杂度NlogN 可以继续优化，因为是取第k个，所以每次算出中值下标后与k比较，这样可以判断出第k大的数位于左边还是右边，将规模降低。 时间复杂度O(n)
超过一半的数 解题思路 方法一： 排序，超过一半的数必然会占据中间位置，直接取排序后的中间位置的数 方法二： 遍历，以第一个数为为基准，记录基准出现的次数，当后面数与基准不同时，计数减一，相同时计数加一，当计数为0后，以下一个数为基数继续计数，遍历完后，基数即是出现超过一半的数。因为只有它的数量超过一半，在最坏情况下，它与所有其他的数进行抵消，依然会有剩余。
引申： 刚好出现一半的数 思路 数组必然是偶数个，依然使用方法二，如果这个数与其他数刚好间隔分布，那么抵消后计数为0，如果不是刚好间隔分布，那么其他数必然会互相抵消，这个数就会有剩余。对于间隔分布这种情况，可以预见倒数第一位与倒数第二位必然有一个是目标数，所以遍历的时候，每次都将当前数与最后一个数进行比较，记录相同的次数，次数等于数组一半或未超过一半，均可确定目标数。
合并有序数组 给定两个排好序的数组A和B，其中A末端有足够的空间容纳B，将B合并到A并排序 思路： 这里用到了归并排序的合并数组，不同的是，这里是从尾端排队插入。
逆序对个数 一个数列如果左边的数大右边的数小则为一个逆序对，求一个数列中有多少个逆序对 利用归并排序升序排序，在merge的时候，如果选择的是右边数组的数，那么这个数比左边数组剩下的数都小，那么与他们都可以组成逆序对。
排序数组中找和的因子 给定以排序的数组arr和k,不重复的打印arr中所有相加和为k的不降序二元组 思路：左右指针向中间逼近 三元组：先确定一个数，这样就降低成二元组了 时间复杂度 n*n