快速排序
什么是快速排序
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：
挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。
选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。
——*
*上说得很详细！
性能分析
- 时间复杂度
快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)
——百度百科
百度百科上说得通俗易懂哈哈！
- 空间复杂度：
快速排序需要一个栈来实现递归。最好情况下，递归树的高度为log2n，因此空间复杂度为O(logn)。最坏情况下树的高度为n，因此空间复杂度为O(n)
实现原理
快速排序选用数组作为存储结构，是一种稳定排序
因为采用了分治策略，所以快速排序的方法可以分为递归法和非递归法(用栈实现)
递归法很好理解吧，从快排的算法步骤可以很明显看出；非递归法就是要自己创建一个栈，来代替递归法中系统调用的函数栈，也没什么难的，就是写起来复杂点！
需要解决的核心问题是：基准元素的选择，以及元素的交换
基准元素的选择
前面说过基准元素的选择十分重要，直接决定算法时间性能。常见的选择规则有：
-
三者取中法：在当前区间上，选择区间首、尾和中间位置上的元素进行比较，选取三者中的中值作为基准
-
随机数法
选择位于low和high中间的随机数k，用array[k]作为基准…
元素的交换
实现元素的交换有三种方法：
- 双边循环法
- 单边循环法
- 挖坑法
具体的步骤就不描述了，网上有很多。直接上代码：
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class QuickSort {
//双边循环法进行快速排序，采用递归
public static void quickSort1(int[] array, int startIndex, int endIndex){
if (startIndex>=endIndex){
return;
}
// int pivotIndex = partition1(array, startIndex, endIndex);
int pivotIndex = partition2(array, startIndex, endIndex);
quickSort1(array, startIndex, pivotIndex-1);
quickSort1(array,pivotIndex+1, endIndex);
}
/**
* 分治（双边循环法），左右指针法交换元素
* @param array 待交换的数组
* @param startIndex 起始坐标
* @param endIndex 结束坐标
* @return 返回指针重合点坐标
*/
private static int partition1(int[] array, int startIndex, int endIndex){
// 这里直接选取第一个位置的元素作为基准元素，一般需要随机选取
int pivot = array[startIndex];
int left = startIndex;
int right = endIndex;
while (left!=right){
while (left<right && array[right]>pivot){
right--;
}
while (left<right && array[left]<=pivot){
left++;
}
//交换元素
if (left<right){
int p = array[left];
array[left] = array[right];
array[right] = p;
}
}
//pivot和指针重合点交换
array[startIndex]=array[left];
array[left] = pivot;
return left;
}
/**
* 分治（双边循环法），挖坑法更新元素
* @param array 待交换的数组
* @param startIndex 起始坐标
* @param endIndex 结束坐标
* @return 返回分界位置
*/
private static int partition2(int[] array, int startIndex, int endIndex){
//还是选择起始元素作为基准元素
int pivot = array[startIndex];
int left = startIndex;
int right = endIndex;
while (left!=right){
while (left<right && array[right]>pivot){
right--;
}
if (left<right){
array[left] = array[right];//right位置成为了一个新坑！
}
while (left<right && array[left]<=pivot){
left++;
}
if (left<right){
array[right] = array[left];//left位置又成为了新坑！
}
}
array[left] = pivot;
return left;
}
//单边循环法实现快速排序，采用递归
public static void quickSort2(int[] array, int startIndex, int endIndex){
if (startIndex>=endIndex){
return;
}
int pivotIndex = partitionV2(array, startIndex, endIndex);
quickSort2(array, startIndex, pivotIndex-1);
quickSort2(array, pivotIndex+1, endIndex);
}
/**
* 分治（单边循环法）
* @param array 待交换的数组
* @param startIndex 起始坐标
* @param endIndex 结束坐标
* @return 返回分界位置
*/
private static int partitionV2(int[] array, int startIndex, int endIndex){
//这里还是选择第一个位置元素作为基准元素！
int pivot = array[startIndex];
int mark = startIndex;
for (int i=startIndex+1;i<=endIndex;i++){
if (array[i]<pivot){
mark++;
int p = array[mark];
array[mark] = array[i];
array[i] = p;
}
}
array[startIndex] = array[mark];
array[mark] = pivot;
return mark;
}
//利用栈，实现快速排序
public static void quickSortWithStack(int[] array, int startIndex, int endIndex){
//利用集合栈来代替递归的函数栈
Stack<Map<String, Integer>> quickSortStack = new Stack<>();
//整个数列的起止坐标，以哈希的形式入栈
Map rootParam = new HashMap();
rootParam.put("startIndex",startIndex);
rootParam.put("endIndex",endIndex);
quickSortStack.push(rootParam);
//循环结束条件：栈为空
while (!quickSortStack.isEmpty()){
//栈顶元素出栈，得到起止下标
Map<String, Integer> param = quickSortStack.pop();
int pivotIndex = partitionV2(array, param.get("startIndex"), param.get("endIndex"));
//根据基准元素分成两部分，把每一部分的起止下标入栈
if (param.get("startIndex")<pivotIndex-1){
Map<String, Integer> leftParam = new HashMap<>();
leftParam.put("startIndex",param.get("startIndex"));
leftParam.put("endIndex",pivotIndex-1);
quickSortStack.push(leftParam);
}
if (pivotIndex+1<param.get("endIndex")){
Map<String, Integer> rightParam = new HashMap<>();
rightParam.put("startIndex",pivotIndex+1);
rightParam.put("endIndex",param.get("endIndex"));
quickSortStack.push(rightParam);
}
}
}
public static void main(String[] args) {
int[] array = new int[]{4,4,6,5,3,2,8,1};
quickSort1(array,0,array.length-1);
System.out.println(Arrays.toString(array));
array = new int[]{4,4,6,5,3,2,8,1};
quickSort2(array,0,array.length-1 );
System.out.println(Arrays.toString(array));
array = new int[]{4,4,6,5,3,2,8,1};
quickSortWithStack(array,0,array.length-1 );
System.out.println(Arrays.toString(array));
}
}