深刻理解快速排序

2023-12-26 21:54:28

理解快速排序的关键在于理解它「分区」的过程。

下面以数组 [4, 1,?5,?3,?6,?2,?7,?8] 为例分析分区的过程。

假设数字 3 被随机选中称为中间值,该数字被交换到数组的尾部。接下来初始化两个指针,指针 P1?初始化至下标为 -1 的位置,指针 P2?初始化至下标为 0 的位置,如「图a」所示。「始终」将指针 P1?指向已经发现的「最后一个」小于 3 的数字。此时尚未发现任何一个小于 3 的数字,因此将指针 P1 指向一个无效的位置。将指针 P2 从下标为 0 的位置开始向右扫描数组中的每个数字。当指针 P2?指向第 1 个小于 3 的数字 1 时,指针 P1?向右移动一格,然后交换两个指针指向的数字,此时数组(即两个指针)的状态如「图b」所示。继续右移指针 P2?直到遇到下一个小于 3 的数字 2,指针 P1?再次向右移动一格,然后交换两个指针指向的数字,此时数组(即两个指针)的状态如「图c」所示。继续右移指针 P2?直到指向数字 3 也没有遇到新的小于 3 的数字,此时整个数组都已经扫描完毕。再次将指针 P1?向右移动一格,然后交换指针 P1?和 P2?指向的数字,于是所有小于 3 的数字都位于 3 的左边,所有大于 3 的数字都位于数组的右边,如「图d」所示。

附上 Java 代码:

public class MyQuicksort {
    /**
     * quicksort - 快排
     */
    private void quicksort(int[] nums, int start, int end) {
        if (end > start) {
            // pivot 为分区完成的下标值(分区 - 目标值左边的数字都小于它,目标值右边的数字都大于它)
            int pivot = partition(nums, start, end);
            // 分治思想,继续分别分区左右边的数组
            quicksort(nums, start, pivot - 1);
            quicksort(nums, pivot + 1, end);
        }
    }

    /**
     * partition - 分区
     * 选取一个随机下标,并把小于和大于的数值分区
     * 分区 - 目标值左边的数字都小于目标值,目标值右边的数字都大于目标值
     */
    private int partition(int[] nums, int start, int end) {
        // 随机一个下标并放置到数组末尾(随机的时间复杂度较平均)
        int random = new Random().nextInt(end - start + 1) + start;
        swap(nums, random, end);

        // small 为 p1 指针的下标。
        // * p1 指针始终指向已经发现的最后一个小于目标值的数字
        int small = start - 1;
        // i 为 p2 指针下标,遍历找到小于目标的数字后,p1 指针前移并交换。使小于目标值的都分区在左边
        for (int i = start; i < end; i++) {
            if (nums[i] < nums[end]) {
                small++;
                swap(nums, small, i);
            }
        }

        // p2 指针遍历完成后,所有小于目标值的数组都在 p1 指针及其左边,此时 p1 指针右移并与目标值交换达成目的
        small++;
        swap(nums, start, end);

        return small;
    }

    /**
     * 交换两个下标的值
     */
    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

文章来源:https://blog.csdn.net/sora_2021/article/details/135230892
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。