快速排序的思想

文字描述

① 首先随机选取一个值作为 Basic 基准点;
② 将大于 基准点 的值放到 Basic 基准点的右边;
③ 将小于 基准点 的值放到 Basic 基准点的左边;
④ 分别对左子序列和右子序列重复前三步
⑤ 直到左子序列和右子序列的长度都为 1 时,排序完成。

图形化描述

1、需要进行快速排序的序列:
需要快速排序的序列
2、随机选取一个值作为 Basic 基准点(为了方便,这里选每次取首个值作为中心轴),同时 Left 左指针指向序列的首个元素, Right 右指针指向序列的末尾元素。
快速排序前的准备

3、Right 右指针先向左移动,只要找到所指向的值小于基准点的值就停下来,即找到小于 7 的数值的位置;然后 Left 左指针再向右移动,找到大于基准点的值就停下来,即找到大于 7 的数值的位置;
指针找到的第一对值

4、将 Left 指针所指向的值与 Right 指针所指向的值互换。
交换两个指针的数值
5、重复步骤3、4。Right 指针再向左移动找到小于基准点的值,Left 指针向右移动找到大于基准点的值。
指针找到的第二对值
然后再将两个值互换。
交换值
6、Right 指针向左移动,找到比基准点小的值 3,Left 指针向右移动,在移动的过程中遇到了 Right 指针,此时第一轮快速排序结束。
两指针相遇
然后将 Left 指针与 Right 指针共同指向的值 3 与基准点的值 7 互换位置。
交换基准点的值与两指针所指向的值
7、通过第一轮快速排序所得到的结果:
第一轮快速排序的结果
8、再对左子序列和右子序列分别进行上述步骤,直到得到的左子序列和右子序列的长度都是 1 时,最后得到的整个序列即使用快速排序完成之后的序列。

代码实现

public class QuickSort{

    public static void sort(int[] a) {
    
        // 判断数组是否可用
        if (a.length > 0) {
            sort(a, 0, a.length - 1);
        }
    }

    public static void sort(int[] a, int left, int right) {

        int i = left;
        int j = right;

        // 防止下标越界
        if (i > j) {
            return;
        }

        // 取首个元素为基准点
        int k = a[left];

        while (i < j) {

            // right 指针向左移动,找到小于基准点值的数的位置
            while (i < j && a[j] > k) {
                j--;
            }

            // left 指针向右移动,找到大于基准点值的数的位置
            while (i < j && a[i] <= k) {
                i++;
            }

            if (i < j) {
                // 交换两个指针所对应的值
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }

        // 当 i=j 时,将两个指针共同指向的值和基准点值交换
        a[left] = a[i];
        a[i] = k;
        

        // 对左子序列进行快速排序,使用递归
        sort(a, left, i - 1);

        // 对右子序列进行快速排序,使用递归
        sort(a, i + 1, right);
    }


    public static void main(String[] args) {
        int[] arr = {6, 1, 77, 4, 5, 10, 7};
        System.out.println(Arrays.toString(arr));

        sort(arr);

        System.out.println(Arrays.toString(arr));
    }
}
最后修改:2021 年 09 月 30 日 04 : 53 PM
如果觉得我的文章对你有用,请随意赞赏