快速排序
一、快排算法有什么优点，为什么称之为“快”排？
QuickSort是对归并排序算法的优化，继承了归并排序的优点，同样应用了分治思想。
1.如何“分”？（如何缩小问题的规模）
2.如何“治”？（如何解决子问题）
快排的前身是归并，归并的最大问题是需要额外的存储空间，并且由于合并过程不确定，致使每个元素在序列中的最终位置上不可预知的。针对这一点，快速排序提出了新的思路：把更多的时间用在“分”上，而把较少的时间用在“治”上。从而解决了额外存储空间的问题，并提升了算法效率。
快排之所以被称为“快”排，是因为它在平均时间上说最快的，主要原因是每趟快排需要指定一个“基准值”（也就是作为分界点的值），一趟中涉及的所有比较都是与这个“基准值”来进行比较的，效率自然大大提高。除此之外，快排的高效率与分治思想也是分不开的。
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
二、如何“分”？（即如何确定“基准值”）
确定一个“基准值”，将数组分为两个部分（比基准值小的 | 比基准值大的）
如何确定这个基准值呢？
1、随机
在所要排序的数组中，随机选取一个数来作为基准值，需要将其交换到最边上。
2、直接取最边上的值（任选左右）。
3、三数取中法
因为前两种取值方法，有大概率取到要排数组的最大值或者最小值，导致所分的两部分的其中一侧没有元素（选取最边上的元素作为基准值，并且数组已经有序或数组逆序，都是最坏情况），为了避免出现这种情况，我们采用三数取中法。
在[ left, left +(right -left)/2, right ] 中，通过判断，选取其中大小为 中 的元素。
例如：9 8 3 4 5 7 2 其下标 0~6 ，left = 0,mid = 3,right = 6; 比较array[left] ,array[mid] ,array[right],得到基准值为“4”。这样就有效避免了取到 极值 的可能。
代码如下：
private static int 三数取中(int[] array,int left, int right) {
int mid = left +(right -left)/2;
if (array[left] > array[right]){
if(array[left] < array[mid]){
return left;
}else if (array[mid] > array[right]){
return mid;
}else{
return right;
}
}else{
if (array[right] < array[mid]){
return right;
}else if(array[mid] > array[left]){
return mid;
}else{
return left;
}
}
}
如何将比基准值小的放左，大的放右？
1、Hover
代码如下：
//1、Hover
private static int parition_01(int[] array,int left,int right){
int begin = left;
int end = right;
int pivot = array[right];
while (begin < end){
while (begin begin++; } while (begin < end && array[end] >= pivot){ end--; } Swap(array,begin,end); } Swap(array,begin,right); return begin; } Swap： private static void Swap(int array[],int a,int b){ int t = array[a]; array[a] = array[b]; array[b] = t; } 2、挖坑法 代码如下： //2、挖坑法 private static int parition_02(int[] array,int left,int right){ int begin = left; int end = right; int pivot = array[right]; while (begin < end){ while (begin begin++; } array[end] = array[begin]; while (begin < end && array[end] >= pivot){ end--; } array[begin] = array[end]; } array[begin] = pivot; return begin; } 3、前后下标 代码如下： //3、前后下标 private static int parition_03(int[] array,int left,int right){ int back = left; int pivot = array[right]; for (int i = left; i <= right; i++){ if(array[i] < pivot){ Swap(array,back,i); back++; } } Swap(array,back,right); return back; } 三、如何“治”？（怎么处理已经分好了的区间） 代码如下： private static void quickSortInner(int[] array, int left, int right) { // 直到 size == 1 || size == 0 if (left == right) { // size == 1 return; } if (left > right) { // size == 0 return; } // 要排序的区间是 array [left, right] // 1. 找基准值，array[right]; int originIndex = sanShuQuZhong(array, left, right); swap(array, originIndex, right); // 2. 遍历整个区间，把区间分成三部分 int pivotIndex = partition3(array, left, right); // 比基准值小的 [left, pivotIndex - 1] // 比基准值的 [pivotIndex + 1, right] // 3. 分治算法 // 处理比基准值小的区间 quickSortInner(array, left, pivotIndex - 1); // 处理比基准值大的区间 quickSortInner(array, pivotIndex + 1, right); } public static void quickSort(int[] array) { quickSortInner(array, 0, array.length - 1); } 快速排序总结： 1.时空复杂度：快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。 实际应用中，快速排序的平均时间复杂度为O(nlogn)。快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度为 O(log（n）)。但需要注意递归栈上需要花费最少logn最多n的空间。 2.稳定性：不稳定