快速排序的俩种实现

算法描述

  1. 每一轮排序选择一个基准点(pivot)进行分区
    1. 让小于基准点的元素的进入一个分区,大于基准点的元素的进入另一个分区
    2. 当分区完成时,基准点元素的位置就是其最终位置
  2. 在子分区内重复以上过程,直至子分区元素个数少于等于 1,这体现的是分而治之的思想 (divide-and-conquer

从以上描述可以看出,一个关键在于分区算法,常见的有单边循环(洛穆托分区方案)、双边循环分区方案、霍尔分区方案

单边循环

核心思路

1,选择数组最右侧元素作为基准点

例如下图中的数组最右侧元素作为基准点。

2,数组从左到右依次遍历元素,比基准点小的放置到基准点左边,比基准点大的放置到基准点右边

达到的效果如下图:

3,步骤 2 之后,基准点将原数组拆分成了俩个子集合。将俩个子集合看作新的集合,重复步骤1,2,直到子集合不能再拆分为止即可完成排序。

代码思路

如图示中,使用俩个游标初始值是数组的最左侧位置。

  1. 选择最右元素作为基准点元素

  2. j 指针负责找到比基准点小的元素,一旦找到则与 i 进行交换,i++

  3. i 指针维护小于基准点元素的边界,也是每次交换的目标索引

  4. 最后基准点与 i 交换,i 即为分区位置

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class QuickSort1 {

public static void main(String[] args) {
int[] arr = {5, 3, 7, 2, 9, 8, 1, 4};
System.out.println(Arrays.toString(arr));
// 第一遍排序全数组
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}

private static void quickSort(int[] arr, int low, int high) {
// 地位大于等于高位则不需要进行排序,结束递归
if(low >= high) {
return;
}
// 完成第一遍,将数组按照基准点进行拆分,并得到基准点的索引位置
int p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}

private static int partition(int[] arr, int low, int high) {
int pv = arr[high];

int i = low;

for (int j = low; j < high; j++) {
if (arr[j] < pv) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, high);
return i;
}

private static void swap(int[] arr, int i, int j) {
if (i != j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}

双边循环

核心思路

1,选择数组最左侧元素作为基准点

2,使用游标分别从数组的俩端往中间移动,左侧游标找比基准点小的,右侧游标找基准点大的,一旦找到就俩者游标对应的元素互换,直到俩个游标相遇为止。

3,俩个游标相遇的位置就是分区的位置。

代码思路

  1. 选择最左元素作为基准点元素
  2. j 指针负责从右向左找比基准点小的元素,i 指针负责从左向右找比基准点大的元素,一旦找到二者交换,直至 i,j 相交
  3. 最后基准点与 i(此时 i 与 j 相等)交换,i 即为分区位置

要点

  1. 基准点在左边,并且要先 j 后 i

  2. while( i < j && a[j] > pv ) j–

  3. while ( i < j && a[i] <= pv ) i++

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class QuickSort2 {

public static void main(String[] args) {
int[] arr = {5, 3, 7, 2, 9, 8, 1, 4};
System.out.println(Arrays.toString(arr));
// 第一遍排序全数组
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}

private static void quickSort(int[] arr, int low, int high) {
// 地位大于等于高位则不需要进行排序,结束递归
if(low >= high) {
return;
}
// 完成第一遍,将数组按照基准点进行拆分,并得到基准点的索引位置
int p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}

private static int partition(int[] arr, int low, int high) {
int pv = arr[low];

int i = low;
int j = high;
while (i < j) {
// 直到 arr[j] 小于等于基准点
while (i < j && arr[j] > pv) {
j--;
}

// 直到 arr[i] 大于基准点
while (i < j && arr[i] <= pv) {
i++;
}
// 上述俩个while循环保证了 i 和 j 一定会相遇,相遇则互换
swap(arr, i, j);
}

// j 的位置就是分区索引位置
swap(arr, low, j);
return j;
}
}
updated updated 2022-02-13 2022-02-13
本文结束感谢阅读

本文标题:快速排序的俩种实现

本文作者:木鲸鱼

微信公号:木鲸鱼 | woodwhales

原始链接:https://woodwhales.cn/2022/02/13/084/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%