基础篇——快速排序_快速排序 csdn

作者：知新_RL | 2024-07-13 16:13:05

踩

快速排序 csdn

快速排序

要求
算法描述
算法实现
其他排序代码补充

要求

能够用自己语言描述快速排序算法
掌握手写单边循环、双边循环代码之一
能够说明快排特点
了解洛穆托与霍尔两种分区方案的性能比较

算法描述

每一轮排序选择一个基准点（pivot）进行分区
1. 让小于基准点的元素的进入一个分区，大于基准点的元素的进入另一个分区
2. 当分区完成时，基准点元素的位置就是其最终位置
在子分区内重复以上过程，直至子分区元素个数少于等于 1，这体现的是分而治之的思想（divide-and-conquer）
从以上描述可以看出，一个关键在于分区算法，常见的有洛穆托分区方案、双边循环分区方案、霍尔分区方案

算法实现

单边循环快排（lomuto 洛穆托分区方案）

算法描述

选择最右元素作为基准点元素
j 指针负责找到比基准点小的元素，一旦找到则与 i 进行交换
i 指针维护小于基准点元素的边界，也是每次交换的目标索引
最后基准点与 i 交换，i 即为分区位置

图形化展示

在这里插入图片描述

代码展示

public static void quick(int[] a, int l, int h) {
    if (l >= h) {
        return;
    }
    int p = partition(a, l, h); // p 索引值
    quick(a, l, p - 1); // 左边分区的范围确定
    quick(a, p + 1, h); // 左边分区的范围确定
}

private static int partition(int[] a, int l, int h) {
    int pv = a[h]; // 基准点元素
    int i = l;
    for (int j = l; j < h; j++) {
        if (a[j] < pv) {
            if (i != j) {
                swap(a, i, j);
            }
            i++;
        }
    }
    if (i != h) {
        swap(a, h, i);
    }
    System.out.println(Arrays.toString(a) + " i=" + i);
    // 返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的边界
    return i;
}

public static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
}
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

双边循环快排（不完全等价于 hoare 霍尔分区方案）

算法描述

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

要点

基准点在左边，并且要先 j 后 i
while( i < j && a[j] > pv ) j–
while ( i < j && a[i] <= pv ) i++

图形化展示

在这里插入图片描述

算法展示

private static void quick(int[] a, int l, int h) {
    if (l >= h) {
        return;
    }
    int p = partition(a, l, h);
    quick(a, l, p - 1);
    quick(a, p + 1, h);
}

private static int partition(int[] a, int l, int h) {
    int pv = a[l];
    int i = l;
    int j = h;
    while (i < j) {
        // j 从右找小的
        while (i < j && a[j] > pv) {
            j--;
        }
        // i 从左找大的
        while (i < j && a[i] <= pv) {
            i++;
        }
        swap(a, i, j);
    }
    swap(a, l, j);
    System.out.println(Arrays.toString(a) + " j=" + j);
    return j;
}
public static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
}
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

快排特点

平均时间复杂度是 $O(nlog_2⁡n )$ ，最坏时间复杂度 $O(n^2)$
数据量较大时，优势非常明显
属于不稳定排序

洛穆托分区方案 vs 霍尔分区方案

霍尔的移动次数平均来讲比洛穆托少3倍
https://qastack.cn/cs/11458/quicksort-partitioning-hoare-vs-lomuto

其他排序代码补充

空穴法改进的双边快排

import java.util.Arrays;

// 空穴法(双边循环法改进)
@SuppressWarnings("all")
public class QuickSort3 {
    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        System.out.println(Arrays.toString(a));
        quick(a, 0, a.length - 1);
    }

    private static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h);
        quick(a, l, p - 1);
        quick(a, p + 1, h);
    }

    private static int partition(int[] a, int l, int h) {
        int pv = a[l];
        int i = l;
        int j = h;
        while (i < j) {
            // j 从右找小的
            while (i < j && a[j] > pv) {
                j--;
            }
            if (i < j) {
                a[i] = a[j];
                i++;
            }
            // i 从左找大的
            while (i < j && a[i] <= pv) {
                i++;
            }
            if (i < j) {
                a[j] = a[i];
                j--;
            }
        }
        a[j] = pv;
        System.out.println(Arrays.toString(a) + " j=" + j);
        return j;
    }
}

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
46
47
48

霍尔分区

import java.util.Arrays;

public class QuickSortHoare {
    public static void main(String[] args) {
//        int[] a = {1,2,3};
//        int[] a = {9, 3, 2, 1};
//        int[] a = {9, 3, 7, 2, 5, 8, 1, 4};
        int[] a = {1, 2, 3, 4, 5, 7, 8, 9};
        System.out.println(Arrays.toString(a));
        quick0(a, 0, a.length - 1);
    }

    private static void quick0(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h);
        colorPrint(a, l, p, p + 1, h);
        // 注意如果左边界选择了 p-1, 则会因为返回的 p 可能不是基准点位置导致出错
        quick0(a, l, p);
        quick0(a, p + 1, h);
    }

    private static void colorPrint(int[] a, int r1l, int r1h, int r2l, int r2h) {
        System.out.print("[");
        for (int i = 0; i < a.length; i++) {
            if (i >= r1l && i <= r1h) {
                System.out.print("\033[31m" + a[i] + "\033[0m");
            } else if (i >= r2l && i <= r2h) {
                System.out.print("\033[34m" + a[i] + "\033[0m");
            } else {
                System.out.print("_");
            }
            if (i < a.length - 1) {
                System.out.print(" ");
            }
        }
        System.out.println("]");

    }

    private static int partition(int[] a, int l, int h) {
//        int pv = a[l];
        int pv = a[(l + h) >>> 1];
        System.out.println("pv=" + pv);
        int i = l - 1;
        int j = h + 1;
        while (true) {
            while (a[++i] < pv) {
            }
            while (a[--j] > pv) {
            }
            if (i >= j) {
                return j;
            }
            swap(a, i, j);
        }
    }
}

public static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
}

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

四种分区实现的移动次数比较

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

public class LomutoVsHoare {

    public static void main(String[] args) {
        List<int[]> all1 = new ArrayList<>();
        List<int[]> all2 = new ArrayList<>();
        List<int[]> all3 = new ArrayList<>();
        List<int[]> all4 = new ArrayList<>();
        for (int i = 0; i < 20; i++) {
            int[] array = Utils.randomArray(10000);
            all1.add(array);
            all2.add(Arrays.copyOf(array, array.length));
            all3.add(Arrays.copyOf(array, array.length));
            all4.add(Arrays.copyOf(array, array.length));
        }
        System.out.println("hoarePartition");
        testPartition(all1, LomutoVsHoare::hoarePartition);
        System.out.println("LomutoPartition");
        testPartition(all2, LomutoVsHoare::LomutoPartition);
        System.out.println("otherPartition");
        testPartition(all3, LomutoVsHoare::otherPartition);
        System.out.println("moveInsteadSwapPartition");
        testPartition(all4, LomutoVsHoare::moveInsteadSwapPartition);
    }

    private static void testPartition(List<int[]> all, FourConsumer consumer) {
        List<AtomicInteger> cs = new ArrayList<>();
        for (int[] array : all) {
            AtomicInteger c = new AtomicInteger();
            consumer.apply(array, 0, array.length - 1, c);
            cs.add(c);
        }
        // 打印的是平均移动次数，而非交换次数，一次交换有3次移动
        System.out.println(cs + " avg:" + cs.stream().mapToLong(AtomicInteger::get).average().orElse(0));
    }

    interface FourConsumer {
        void apply(int[] a, int b, int c, AtomicInteger d);
    }

    private static int hoarePartition(int[] a, int l, int h, AtomicInteger c) {
//        int pv = a[l];
        int pv = a[(l + h) >>> 1];
        int i = l - 1;
        int j = h + 1;
        while (true) {
            while (a[++i] < pv) {
            }
            while (a[--j] > pv) {
            }
            if (i >= j) {
                return j;
            }
            c.accumulateAndGet(3, Integer::sum);
            swap(a, i, j);
        }
    }

    private static int LomutoPartition(int[] a, int l, int h, AtomicInteger c) {
        int pv = a[h];
        int i = l;
        for (int j = l; j < h; j++) {
            if (a[j] < pv) {
                if (i != j) {
                    c.accumulateAndGet(3, Integer::sum);
                    swap(a, i, j);
                }
                i++;
            }
        }
        if (i != h) {
            c.accumulateAndGet(3, Integer::sum);
            swap(a, h, i);
        }
        return i;
    }

    private static int otherPartition(int[] a, int l, int h, AtomicInteger c) {
        int pv = a[l];
        int i = l;
        int j = h;
        while (i < j) {
            while (i < j && a[j] > pv) {
                j--;
            }
            while (i < j && a[i] <= pv) {
                i++;
            }
            c.accumulateAndGet(3, Integer::sum);
            swap(a, i, j);
        }
        c.accumulateAndGet(3, Integer::sum);
        swap(a, l, i);
        return i;
    }

    private static int moveInsteadSwapPartition(int[] a, int l, int h, AtomicInteger c) {
        int pv = a[l];
        int i = l;
        int j = h;
        while (i < j) {
            // j 从右找小的
            while (i < j && a[j] > pv) {
                j--;
            }
            if (i < j) {
                c.incrementAndGet();
                a[i] = a[j];
                i++;
            }
            // i 从左找大的
            while (i < j && a[i] <= pv) {
                i++;
            }
            if (i < j) {
                c.incrementAndGet();
                a[j] = a[i];
                j--;
            }
        }
        c.incrementAndGet();
        a[j] = pv;
        return j;
    }
    
    public static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
     }

}

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/820379