​
​

活动地址：CSDN21天学习挑战赛

怕什么真理无穷，进一步有一份的欢喜。

【21天学习挑战赛】快速排序

✌我为什么参与挑战赛

1，机缘

读到研一了，暑假假期打开私信发现这个挑战赛就鼓起勇气参加了。

2，期待的收获

A, 本人在华南理工大学攻读专硕，目前研究方向是图像恢复，从事深度学习相关工作，目标是从事Java后端开发。
B, 期待您的反馈，如果有什么不对的地方，欢迎指正！
C, 期待认识志同道合的领域同行或技术交流。
如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

🍉快速排序的图解

快速排序是一种划分交换排序方法，采用了分治策略。首先将原问题划分成若干个规模更小、与原问题相似的子问题，然后用递归方法解决这些子问题，最后再将它们组合成原问题的解。
第一趟排好序列中的一个数，放在它应该在的位置上，同时得到两个子序列，左侧都是比它小的数，右侧都是比它大的数（升序排序时）。接下来在每个子序列中不断重复归位一个元素、得到子序列这个过程，直到子序列的长度为1或0，此时整体的序列已经有序

• （a）将待排元素选定为序列的最后一个元素:4，目标是在左侧的无序区中划分出两个子序列。
  • p为序列区间左端点，r为序列区间右端点。
    i的初始值在区间端点之前，用于划分出较小元素所在区间。
    j为进行扫描时使用的变量，每次取到元素进行判断，然后进行区间的调整。
  • i所在的部分构成橙色区域（较小数区间），i与j之间的部分构成蓝色区域（较大数区间）。
• （b）2 < 4，应归入较小数区间，i进行后移（此时i与j指向同一元素），并与j指向的元素交换，橙色区域增加。
• （c）8 > 4，应归入较大数区间，j正常后移，蓝色区域增加。
• （d）7 > 4，应归入较大数区间，j正常后移，蓝色区域增加。

• （e）1 < 4，应归入较小数区间，i进行后移，并与j指向的元素交换，橙色区域增加。

• （f）3 < 4，应归入较小数区间，i进行后移，并与j指向的元素交换，橙色区域增加。

• （g）5 > 4，应归入较大数区间，j正常后移，蓝色区域增加。

• （h）6 > 4，应归入较大数区间，j正常后移，蓝色区域增加。
  

• （i）此时j已达到边界，最后只需要将深色区域的首个元素（8）与待排元素（4）交换。

💬快速排序的定义

快速排序是在待排序列中取一个元素（比如最后一个）作为参照，将序列分为两个子序列，比参照值小的元素和比参照值大的元素各自组成一个子序列。每趟排序会使参照元素归位，并得到两个子序列。在子序列中继续执行该步骤，直到子序列的长度为0或1。

✨快速排序的优劣

优势

对于快速排序来说，是基于关键字比较的内部排序算法中速度最快的，平均性能可以达到O(nlog2n)。

劣势

实现复杂，由于使用到了递归操作，空间复杂度较高，在平均情况下，需要O(log2n)，在最坏的情况下，不会超过O(n)

🍵快速排序的步骤

1. 第一趟排好序列中的一个数
2. 得到左侧子序列，左侧都是比它小的数
3. 得到右侧子序列，右侧都是比它大的数
4. 递归调用

✍️ 算法实现

public class QuickSort {

    public static void main(String[] args) {
        // input data
        int[] a = {2,8,7,1,3,5,6,4};
        // 调用快速排序，传入初始的左右端点
        quickSort(a,0,a.length - 1);
        // 查看排序结果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }

    private static int partition(int[] a,int p,int r){
        // 声明待排元素
        int x = a[r];
        // 初始化较小数区间端点
        int i = p - 1;
        // 循环结束后，区间已经划定完毕
        for(int j = p;j < r;j++){
            // 将较小的数向前扔
            if(a[j] < x){
                i++;
                // 交换两个元素
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        // 交换待排元素到指定位置
        int tmp = a[i + 1];
        a[i + 1] = a[r];
        a[r] = tmp;
        return i + 1;
    }

    private static void quickSort(int[] a,int p,int r){
        // 重要：递归的出口（终止条件）为区间长度小于1
        if(p < r){
            // 划分后得到已排好元素的位置
            int q = partition(a,p,r);
            // 根据位置得到较小数列区间
            quickSort(a,p,q-1);
            // 根据位置得到较大数序列区间
            quickSort(a,q + 1,r);
        }
    }

}


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

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
⭐️ 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！