快速排序（Quick Sort）
2021-11-20 本文已影响0人
小波同学
一、算法概述
1.1 算法分类
十种常见排序算法可以分为两大类：
-
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
-
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
1.2 算法复杂度
1.3 相关概念
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
二、快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2.1 算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
2.2 动图演示
QuickSort
2.3 排序过程
下面以数列a={30,40,60,10,20,50}为例，演示它的快速排序过程(如下图)。
上图只是给出了第1趟快速排序的流程。在第1趟中，设置x=a[i]，即x=30。
-
01、从"右 --> 左"查找小于x的数：找到满足条件的数a[j]=20，此时j=4；然后将a[j]赋值a[i]，此时i=0；接着从左往右遍历。
-
02、从"左 --> 右"查找大于x的数：找到满足条件的数a[i]=40，此时i=1；然后将a[i]赋值a[j]，此时j=4；接着从右往左遍历。
-
03、从"右 --> 左"查找小于x的数：找到满足条件的数a[j]=10，此时j=3；然后将a[j]赋值a[i]，此时i=1；接着从左往右遍历。
-
04、从"左 --> 右"查找大于x的数：找到满足条件的数a[i]=60，此时i=2；然后将a[i]赋值a[j]，此时j=3；接着从右往左遍历。
-
05、从"右 --> 左"查找小于x的数：没有找到满足条件的数。当i>=j时，停止查找；然后将x赋值给a[i]。此趟遍历结束！
-
按照同样的方法，对子数列进行递归遍历。最后得到有序数组！
三、快速排序分类
快速排序分为：
- 单边循环快排(lomuto 洛穆托分区方案)
- 双边循环快排(并不完全等价于hoare霍尔分区方案)
- hoare霍尔分区方案
这里介绍单边循环快排(lomuto 洛穆托分区方案)和双边循环快排(并不完全等价于hoare霍尔分区方案)
3.1 单边循环快排(lomuto 洛穆托分区方案)
- 1、选择最右元素作为基准点元素
- 2、j指针负责找到比基准点小的元素, 一旦找到则与i进行交换
- 3、i指针维护小于基准点元素的边界, 也是每次交换的目标索引
- 4、最后基准点与i元素交换, i即为分区位置
/**
* @author: huangyibo
* @Date: 2021/11/17 18:38
* @Description: 快速排序——单边循环快排(lomuto 洛穆托分区方案)
* 1、选择最右元素作为基准点元素
* 2、j指针负责找到比基准点小的元素, 一旦找到则与i进行交换
* 3、i指针维护小于基准点元素的边界, 也是每次交换的目标索引
* 4、最后基准点与i元素交换, i即为分区位置
*/
public class QuickSort1 {
public static void main(String[] args) {
int[] arr = {5, 9, 7, 4, 1, 3, 2, 8};
quickSort(arr,0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
//当指定区间范围内元素值小于等于1的时候, 停止递归调用
if(left >= right){
return;
}
//pv 基准点的正确索引值
int pv = partition(arr, left, right);
//左边分区的范围确定
quickSort(arr, left,pv - 1);
//右边分区的范围确定
quickSort(arr, pv + 1, right);
}
public static int partition(int[] arr, int left, int right) {
//基准点元素
int pivot = arr[right];
int i = left;
for (int j = i; j < right; j++) {
if(arr[j] < pivot){
if(i != j){
//i和j不相等的时候才交换元素
swap(arr, i, j);
}
i++;
}
}
if(i != right){
//一轮循环之后，基准点元素和小于基准点元素边界值交换
swap(arr, right, i);
}
//返回值代表了基准点元素所在的正确索引，它确定下一轮分区的边界
return i;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
3.2 双边循环快排(并不完全等价于hoare霍尔分区方案)
- 1、选择最左元素作为基准点元素
- 2、j指针负责从右向左找比基准点小的元素, i指针负责从左向右找比基准点大的元素, 一旦找到二者交换, 直到i、j相交
- 3、最后基准点与i(此时i与j相等)交换, i即为分区位置
/**
* @author: huangyibo
* @Date: 2021/11/17 18:41
* @Description: 快速排序——双边循环快排(并不完全等价于hoare霍尔分区方案)
* 1、选择最左元素作为基准点元素
* 2、j指针负责从右向左找比基准点小的元素, i指针负责从左向右找比基准点大的元素, 一旦找到二者交换, 直到i、j相交
* 3、最后基准点与i(此时i与j相等)交换, i即为分区位置
*
* 特点:
* 1、平均时间复杂度是O(n ㏒₂n), 最坏时间内复杂度为O(n²)
* 2、数据量较大时，优势非常明显
* 3、属于不稳定排序算法
*/
public class QuickSort2 {
public static void main(String[] args) {
int[] arr = {5, 9, 7, 4, 6, 1, 3, 2, 8};
quickSort(arr,0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
//当指定区间范围内元素值小于等于1的时候, 停止递归调用
if(left >= right){
return;
}
//pv 基准点的正确索引值
int pv = partition(arr, left, right);
//左边分区的范围确定
quickSort(arr, left,pv - 1);
//右边分区的范围确定
quickSort(arr, pv + 1, right);
}
public static int partition(int[] arr, int left, int right) {
//基准点元素
int pivot = arr[left];
int i = left;
int j = right;
while (i < j){
//j指针负责从右向左找比基准点小的元素, 必须先从右向左找，先执行j指针
while(i < j && arr[j] > pivot){
j--;
}
//i指针负责从左向右找比基准点大的元素
while(i < j && arr[i] <= pivot){
i++;
}
if(i != j){
//i和j不相等的时候才交换元素
swap(arr, i, j);
}
}
//一轮循环之后, i指针和j指针相交, 基准点元素和j指针(i、j指针相等)元素交换
if(j != left){
swap(arr, left, j);
}
//返回值代表了基准点元素所在的正确索引，它确定下一轮分区的边界
return j;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
3.3 快速排序特点
- 1、平均时间复杂度是O(n ㏒₂n), 最坏时间内复杂度为O(n²)
- 2、数据量较大时，优势非常明显
- 3、属于不稳定排序算法
