【数据结构与算法】快速排序（三种代码实现以及工程优化）
概念
快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两个部分独立地排序。递归调用发生在处理整个数组之后。
快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。[ 比基准值小的数] 基准值 [ 比基准值大的数]
代码实现
单向扫描分区法
- 第一个元素也就是下标low所指元素作为基准值pivot
- 左指针i开始指向第二个元素。
- 右指针j开始指向最后一个元素。
- 如果i所指向元素小于等于pivot，则i向右移动一位
- 如果i所指向元素大于pivot，则i不动，i所指向元素与j所指向元素交换，j向左移动一位
- 最终状态是i和j相邻，并且j位于i的左边，j指向小于等于区域的最后一个元素，i指向大于区域的第一个元素。
- 把pivot和j所指向元素交换，即可把pivot放到中间位置（每个区域内部不用考虑有序性）。
public static void main(String[] args) {
int[] arr = {2, 2, 2, 0, 0, 0, 1};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
private static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length < 2 || high <= low) return;
int j = partition(arr, low, high); //切分
quickSort(arr, low, j - 1); //将左半部分arr[low...j-1]排序
quickSort(arr, j + 1, high); //将右半部分arr[j+1...high]排序
}
private static int partition(int[] arr, int low, int high) {
int i = low + 1, j = high; //左右扫描指针
int pivot = arr[low]; //切分元素，设定基准值为从左向右第一个元素的下标
while (i <= j) {
if (arr[i] <= pivot) //扫描元素小于基准值，左指针右移
i++;
else {
swap(arr, i, j); //扫描元素大于基准值，两个指针的元素交换，右指针左移。使该元素到基准值右侧（确定i所指向元素属于大于区域，那就把它放到大于区域）
j--;
}
} //j最后所指向的位置是小于区域的最后一个元素
swap(arr, low, j); //将基准值插入到相应位置，也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
return j;
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
双向扫描分区法
双向扫描的思路是，头尾指针往中间扫描，从左找到大于主元的元素，从右找到小于等于主元的元素二者交换，继续扫描，直到左侧无大元素，右侧无小元素
- 第一个元素也就是下标low所指元素作为基准值pivot
- 左指针i开始指向第二个元素。
- 右指针j开始指向最后一个元素。
- 开始外层循环，条件是i<=j
- 如果i所指向元素小于等于pivot，则i向右移动一位，循环进行，直到i所指向元素大于等于pivot
- 如果j所指向元素大于pivot，则j向左移动一位，循环进行，直到j所指向元素小于pivot
- 交换i和j所指向元素
- 最终状态是i和j相邻，并且j位于i的左边，j指向小于等于区域的最后一个元素，i指向大于区域的第一个元素。
- 把pivot和j所指向元素交换，即可把pivot放到中间位置（每个区域内部不用考虑有序性）。
public static void main(String[] args) {
int[] arr = {1,5,6,3,2,1,4,5,2};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
private static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length < 2 || high <= low) return;
int j = partition(arr, low, high); //切分
quickSort(arr, low, j - 1); //将左半部分arr[low...j-1]排序
quickSort(arr, j + 1, high); //将右半部分arr[j+1...high]排序
}
private static int partition(int[] arr,int low,int high){
int i = low + 1, j = high; //左右扫描指针
int pivot = arr[low]; //切分元素，设定基准值为从左向右第一个元素
while(i<=j){
while(i<=j&&arr[i]<=pivot) //扫描元素小于基准值，左指针右移（注意保证i<=j）
i++;
while(i<=j&&arr[j]>pivot) //扫描元素大于基准值，右指针左移（注意保证i<=j）
j--;
if(i<j) //注意该处判断
swap(arr,i,j); //左右指针指向元素交换
}
swap(arr,low,j); //将基准值插入到相应位置，也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
return j;
}
private static void swap(int[] arr,int a,int b){
int tmp = arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
有相同元素的快速排序——三分法
双向扫描的思路是，多考虑相等的情况，i 指针从左向右扫描，j 指针从右向左扫描，e永远指向相等区域的第一个元素（小于区域的后面第一个元素）。
- 第一个元素也就是下标low所指元素作为基准值pivot
- 左指针i开始指向第二个元素。
- 右指针j开始指向最后一个元素。
- 中间指针e开始指向第二个元素
- 开始外层循环，条件是i<=j
- 如果i所指向元素小于pivot，i所指向元素和e所指向元素交换（e左边是小于区域，把i的元素放到小于区域），i向右移动一位，e向右移动一位。
- 如果i所指向元素等于pivot，i向右移动一位。（相等于等于区域扩大一位）
- 如果j所指向元素大于pivot，交换i所指向元素和j所指向元素，j左移一位。（相当于把i的元素放到大于区域）
- 最终状态是i和j相邻，并且j位于i的左边，j指向等于区域的最后一个元素，i指向大于区域的第一个元素，e指向等于区域的第一个元素（即小于区域的后面第一个元素）。
- 把pivot和（e-1）所指向元素交换，即可把pivot放到中间位置（每个区域内部不用考虑有序性）。
- 返回等于区域左边第一个元素下标和等于区域右边最后一个元素下标。
public static void main(String[] args) {
int[] arr = {5,2,1,3,6,7};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
private static void quickSort(int[] arr,int low,int high){
if(arr==null||arr.length<2||low>=high) return;
int []j = partition(arr,low,high); //返回两个坐标
quickSort(arr,low,j[0]-1); //将左半部分arr[low...j[0]-1]排序
quickSort(arr,j[1]+1,high); //将右半部分arr[j[0]+1...high]排序
}
private static int[] partition(int[] arr,int low,int high){
int i = low+1;
int j = high;
int pivot = arr[low];
int e = low+1;
while(i<=j){
if(arr[i]<pivot){ //小于pivot，i位置和e位置交换，e++,i++
swap(arr,i,e);
e++;
i++;
}
else if(arr[i]==pivot){ //等于pivot,i++
i++;
}else{
swap(arr,i,j); //大于pivot，s位置和j位置交换，j--
j--;
}
}
swap(arr,low,e-1); //将基准值插入到相应位置
return new int[]{e,j}; //返回等于区域左边第一个元素下标和等于区域右边最后一个元素下标。
}
private static void swap(int[] arr,int a,int b){
int tmp = arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
工程实践中的其他优化
优化策略
分析一下上面的双向扫描分区法，在定义pivot时都指定第一个元素为pivot的值，有可能pivot的值不在数组中居中，有可能退化成O(n^2)时间复杂度。
举个极端情况的例子：
每次选取pivot都为首元素，而pivot的值恰好为最大元素，则pivot最后需要到最右的位置，那么下一次递归调用右半部分arr[j+1…high]就没有了，只有左半部分arr[low…j-1]。而不巧下一次递归pivot选取第一个元素又是最大的，又要重复以上步骤。
数据规模类似从n 到n-1 到n-2 ……到1 ，做n层，最后时间复杂度是O(n^2)级，然而理想的时间复杂度是O(nlogn)级别。
理想情况：
如果每次pivot恰好是中间大小元素，那每次数据规模都变为n/2。写出时间复杂度的递推式：
T(n) = 2T(n/2)+O(n) (O(n)是遍历数组的复杂度，T(n/2)是递归一个分支的复杂度)
利用Master公式：
T(N) = a*T(N/b) + O(N^d)
- log(b,a) > d -> 复杂度为O(N^log(b,a))
- log(b,a) = d -> 复杂度为O(N^d * logN)
- log(b,a) < d -> 复杂度为O(N^d)
其中 a >= 1 and b > 1 是常量，其表示的意义是n表示问题的规模，a表示递归的次数也就是生成的子问题数，b表示每次递归是原来的1/b之一个规模，O(N^d)表示分解和合并等其他操作所要花费的时间复杂度。
使用前提是递归子问题规模相同。
可以得到，a=2,b=2,d=1，log(b,a)=d，复杂度为O(N^d * logN)也就是O(nlogn)
所以我们要做的就是尽力让pivot每次都能选到数组中间大小元素位置。
三点中值法
在low，high，midIndex(low和high的中间元素下标）之间，选一个中间大小值作为主元。
优化一下双向扫描分区法的patition函数：
private static int partition(int[] arr, int low, int high) {
int i = low + 1, j = high; //左右扫描指针
int midIndex = low + ((high - low) >> 2); //中间下标
int midValueIndex = -1; //中值的下标
if ((arr[low] <= arr[midIndex] && arr[high] >= arr[midIndex]) || (arr[low] >= arr[midIndex] && arr[high] <= arr[midIndex]))
midValueIndex = midIndex;
else if ((arr[high] <= arr[low] && arr[midIndex] >= arr[low]) || (arr[high] >= arr[low] && arr[midIndex] <= arr[low]))
midValueIndex = low;
else midValueIndex = high;
swap(arr,low,midValueIndex); //交换中间大小值和low位的值，让pivot依然位于low的位置，但其值变为中间大小值
int pivot = arr[low]; //切分元素，设定基准值为从左向右第一个元素
while (i <= j) {
while (i <= j && arr[i] <= pivot) //扫描元素小于基准值，左指针右移（注意保证i<=j）
i++;
while (i <= j && arr[j] > pivot) //扫描元素大于基准值，右指针左移（注意保证i<=j）
j--;
if (i < j) //注意该处判断
swap(arr, i, j); //左右指针指向元素交换
}
swap(arr, low, j); //将基准值插入到相应位置，也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
return j;
}
三点中值法使用比较广。java中使用三点中值法。
绝对中值法
保证pivot是数组的绝对中值
但会使复杂度的的常数因子扩大，有可能得不偿失。
把数组按照每五个元素为一组分组，使用插入排序选出每组中的中值，再把这些中值放到一个数组中使用插入排序选出中值也就是pivot，将其与low的值做交换，保证程序剩下部分正常运行。
private static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length < 2 || high <= low) return;
int j = partition(arr, low, high); //切分
quickSort(arr, low, j - 1); //将左半部分arr[low...j-1]排序
quickSort(arr, j + 1, high); //将右半部分arr[j+1...high]排序
}
private static int partition(int[] arr, int low, int high) {
int i = low + 1, j = high; //左右扫描指针
int midValueIndex = getMedian(arr, low, high);
swap(arr,midValueIndex,low);
int pivot = arr[low];
while (i <= j) {
while (i <= j && arr[i] <= pivot) //扫描元素小于基准值，左指针右移（注意保证i<=j）
i++;
while (i <= j && arr[j] > pivot) //扫描元素大于基准值，右指针左移（注意保证i<=j）
j--;
if (i < j) //注意该处判断
swap(arr, i, j); //左右指针指向元素交换
}
swap(arr, low, j); //将基准值插入到相应位置，也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
return j;
}
private static int getMedian(int[] arr, int p, int r) { //获取中值方法
int size = r - p + 1; //数组长度
//每五个元素一组
int groupSize = (size % 5 == 0) ? (size / 5) : (size / 5 + 1);
//存储各小组中值
int medians[] = new int[groupSize];
int indexOfMedians = 0;
//对每一组进行插入排序
for (int j = 0; j < groupSize; j++) {
//单独处理最后一组，因为最后一组可能不满5个元素
if (j == groupSize - 1) {
InsertionSort(arr, p + j * 5, r); //排序最后一组
medians[indexOfMedians++] = arr[(p + j * 5 + r) / 2]; //最后一组的中间那个
} else {
InsertionSort(arr, p + j * 5, p + j * 5 + 4); //排序非最后一个组的某个组
medians[indexOfMedians++] = arr[p + j * 5 + 2]; //当前组（排序后）的中间那个
}
}
InsertionSort(medians, 0, medians.length - 1);
return medians[medians.length / 2];
}
private static void InsertionSort(int[] arr,int begin,int end){ //插入排序
if(arr==null||arr.length<2) return; //去除无效情况
for(int i = begin+1; i < end; i++){
for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--)
swap(arr,j,j+1);
}
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
用的较少，看需求。
待排序列表较短时，使用插入排序
插入排序的真实复杂度是n(n-1)/2，快速排序的真实复杂度是n(logn+1)
估计一下：
- n<8 时用插入排序更快
- n>8 时用快排更快
public static void quickSort(int[] A, int p, int r) {
if (p < r) {
//待排序个数小于等于8的时候，插入排序
if (p - r + 1 <= 8) {
InsertionSort(A, p, r); //插入排序
} else { //快排
int q = partition(A, p, r);
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
}
}
}
随机快排
在数组范围中，等概率随机选一个数作为划分值，然后把数组分成三个部分：
左侧<划分值、中间==划分值、右侧>划分值
public static void main(String[] args) {
int[] arr = new int[]{2, 5, 3, 6, 1, 4};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length < 2 || low >= high) return;
int[] j = partition(arr, low, high);
quickSort(arr, low, j[0] - 1);
quickSort(arr, j[1] + 1, high);
}
public static int[] partition(int[] arr, int low, int high) {
int p = (int) Math.random() * (high - low + 1) + low; //随机选取一个基准值
swap(arr, p, low); //把选出的基准值和数组第一个数交换
int i = low + 1;
int j = high;
int pivot = arr[low];
int e = low + 1;
while (i <= j) {
if (arr[i] < pivot) {
swap(arr, i, e);
i++;
e++;
} else if (arr[i] == pivot) {
i++;
} else {
swap(arr, i, j);
j--;
}
}
swap(arr, low, e - 1);
return new int[]{e, j};
}
public static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
题目
奇数在左
调整数组顺序使奇数位于偶数前面:输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
思路：利用双向扫描分区思路，左右指针相向移动，左指针遇到偶数，右指针遇到奇数，左右指针所知指向元素交换，循环直到i>j。
第k个大的元素
以尽量高的效率求出一个乱序数组中按数值顺序的第K个元素值
思路一：先用快速排序法把数组排序，取出第k个元素即可。时间复杂度O(n^2)
思路二（改进）：利用快排的分区partition思想，三点取中法，每次求出一个pivot值将其与目标元素比较大小，pivot就是已经确定数组中绝对位置元素值（利用pivot下标可以计算出其是第几大的数）。若小于目标元素，则只需要递归pivot左侧数组；若大于目标元素，则只需要递归pivot右侧数组。
时间复杂度的递推式：T(N)=T(n/2)+O(n)
利用Master公式
a = 1,b = 2,d = 1 log(b,a)<d，时间复杂度 O(n)，为线性复杂度。
private static int selectK(int[] arr,int low,int high,int k){ //
int q = partition(arr,low,high); //调用双向扫描分区法的partition方法
int qk = q-low+1; //主元是第几大的元素
if(qk==k) return arr[q]; //找到返回
else if(qk>k) return selectK(arr,low,q-1,k); //小于递归左边
else return selectK(arr,q+1,high,k-qk); //大于递归右边，注意k的相对位置变化，要改变坐标，表示右侧数组第几大元素
//相当于剪掉了qk个元素，求第k-qk个元素
}
超过一半的数字
数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
思路一：先用快排，求出中间大小元素即为答案。时间复杂度O(nlogn)
思路二：顺序统计。时间复杂度O(n)
类比上一个题，就是选出k是第中间大的元素
//调用的时候传参k=arr.length/2
private static int selectK(int[] arr,int low,int high,int k){ //
int q = partition(arr,low,high); //调用双向扫描分区法的partition方法
int qk = q-low+1; //主元是第几大的元素
if(qk==k) return arr[q]; //找到返回
else if(qk>k) return selectK(arr,low,q-1,k); //小于递归左边
else return selectK(arr,q+1,high,k-qk); //大于递归右边，注意k的相对位置变化，要改变坐标，表示右侧数组第几大元素
//相当于剪掉了qk个元素，求第k-qk个元素
}
版权声明：本文为gonghr原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。