分治 divide-and-conquer 
递归 
归并排序 mergeSort
快速排序 quickSort

归并排序 核心思想
数组从中间分成左右两部分
左右两部分分别排序
排好序的两部分合并 

稳定排序
时间复杂度 O(nlogn)   最好 最坏 平均情况 都是O(nlogn)
空间复杂度 O(n)  


快速排序 三步走
选择基准值  
将数组分成两个子数组 ， 小于基准值的元素和大于基准值的元素
对两个子数组进行快速排序

非稳定排序
原地排序  不占用额外空间

分区点 基准点 pivot
借助双指针确定pivot位置的分区函数
大部分情况下的时间复杂度为 O(nlogn)  极端情况下退化到 O(n*n)

两个常见快排优化方法

三数取中法
从区间 首 尾 中间 分别取出一个数， 取这 3 个数的中间值作为分区点
随机法