数据结构 ----- 快速排序

​
​​
​​

​ 快速排序

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

一、快速排序

1.1 概念

快速排序是由冒泡排序改进而来的，虽然是由冒泡排序改进而来，但是在排序思想上其实并没有什么必然的联系，只是同属交换排序；
快速排序的排序思想是通过基准值分区，然后将一个大排序分割成一个个小排序，然后再分直至出现一个有序序列；

1.2 查找过程

• 快速排序的排序思路第一件事就是取一个基准值进行比较，我们在这边把每一次排序的第一个元素作为对比的基准值；
• 由下图我们可以看到，在第一轮排序中我们取 9 作为基准值，然后用剩余所有元素跟其进行对比，如果比 9 要小，就将该元素放置在 9 的左方，如果比 9 要大，就将该元素放置在 9 的右边；
• 进行完一轮排序后，我们所使用的基准值已经到达了其最终所在的位置，所以这个值已经不需要参与排序了；
• 根据前一轮所选取的基准值，我们在其左边再进行一次排序，右边也同理再进行一次排序；
• 根据上述规则不断分区，直到整个序列有序之后整个排序就结束了；

图 1.1

1.3 代码演示

1.3.1

• 将需要排序的序列存入数组；
• 建立一个方法，将数组传入、起始坐标传入、终点坐标传入；

图 1.2

1.3.2

• 将基准值传进一个辅助空间；
• 将起始坐标和终点坐标拷贝一份用于遍历；

图 1.3

1.3.3

• 根据基准值进行第一次排序；
• 从右边的点位点开始向前遍历，直到查找到一个小于基准值的元素，并将该值赋值至左边的定位点；（因为最左边元素是作为基准值的，已经拷贝在辅助变量内，所以可以直接替换掉）
• 右边遍历完后再从左边的定位点进行向后遍历，直到查找到一个大于基准值的元素，并将该元素赋值至右边的定位点；
• 直到左边定位坐标最终不小于右边定位坐标时，一次循环结束，然后将基准值传入两个坐标相交的位置；（ 跳出循环的最终条件就是左边定位坐标等于右边定位坐标 ）

图 1.4

1.3.4

• 加入两个递归对左右两个区间进行同样的方式排序；

图 1.5

1.3.5

• 当起始定位坐标不小于终点定位坐标时，就代表无法进行排序了，直接返回；

图 1.5

1.4 代码测试

1. 在每一轮排序结束后添加一个遍历输出序列；
2. 通过每一轮的序列我们可以看出整个排序的过程；
3. 结论：代码可用无误；

图 1.5

1.5 代码分享

public class test {

    public static void main(String[] args) {
        int[] arr = {   15 ,20 , 14 ,   21  ,12 , 9 , 16 , 18 , 10 };
        celerity(arr,0,arr.length-1);

        System.out.println("最终产生的有序序列为：");
        for ( int e: arr ) {
            System.out.print( e + " ");
        }

    }

    private static void celerity(int[] arr,int left,int right) {
        if ( left >= right )
            return;
        int temp = arr[left];
        int i = left,j = right;

        while ( i < j ){
            while ( temp <= arr[j] && j > i )
                j--;
            arr[i] = arr[j];
            while ( temp >= arr[i] && j > i )
                i++;
            arr[j] = arr[i];
        }
        arr[i] = temp;
        celerity(arr,left,i-1);
        celerity(arr,i+1,right);
    }
}
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