软考-软件设计师：排序算法-交换类排序：快速排序

作者：马育民 • • 阅读：10043

介绍

快速排序采用的是 分治法：将原问题分解成 若干个 规模更小但结构与原问题相似的 子问题。通过 递归 解决这些 子问题，然后再将这些 子问题的 解 组合成 原问题的 解。

中心元素（基准元素）

一般选第一个，也可以是中位数，或 最后一个

步骤

  1. 从待排序序列中任取一个元素（例如第一个）作为它的中心元素，比其小（或者相等）的元素放前（左侧），比其大的元素放后面（右侧）。此时得到两组元素

  2. 对两组元素选择中心元素，并比较、调整顺序

  3. 以此类推，直到每组元素只剩一个。此时就是有序序列了

例子

对数组 [6, 3, 8, 2, 9, 1, 11, 5, 10, 8, 12, 8, 7, 4] 进行快速排序（升序）

第1轮

选择 最后元素 4 作为基准元素，与各个元素比较，小的放前，大的放后：

从前往后循环（ 4 除外，因为是基准元素）：

  • 第1个元素 6，比 4 大，不动
  • 第2个元素 3，比 4 小，不动，与第1个元素 6 交换位置，结果：[3, 6, 8, 2, 9, 1, 11, 5, 10, 8, 12, 8, 7, 4, ]
  • 第3个元素 8，比 4 大，不动
  • 第4个元素 2，比 4 小，与第2个元素 6 交换位置，结果：[3, 2, 8, 6, 9, 1, 11, 5, 10, 8, 12, 8, 7, 4, ]
  • 第5个元素 9，比 4 大，不动
  • 第6个元素 1，比 4 小，与第3个元素 8 交换位置，结果：[3, 2, 1, 6, 9, 8, 11, 5, 10, 8, 12, 8, 7, 4, ]
  • 后面元素都比4大，都不动
  • 最后，基准元素 4，与第4个元素 6 交换位置，结果：[3, 2, 1, 4, 9, 8, 11, 5, 10, 8, 12, 8, 7, 6, ]

以 4 为基准，分成两组元素：

  • 比 4 小的：[3, 2, 1,]
  • 比 4 大的：[9, 8, 11, 5, 10, 8, 12, 8, 7, 6, ]

第2轮

对上个结果的 第一组元素 [3, 2, 1,] 进行排序

选择 最后元素 1 作为基准元素，与各个元素比较，小的放前，大的放后，结果：

从前往后循环（ 1 除外，因为是基准元素）：

  • 第1个元素 3，比 1 大，不动
  • 第2个元素 2，比 1 大，不动
  • 最后，基准元素 1，与第1个元素 3 交换位置，结果：[1,2,3]

以 1 为基准，分成一组元素：

  • 比 1 大的：[2,3]

整个序列是：[1, 2, 3, 4, 9, 8, 11, 5, 10, 8, 12, 8, 7, 6, ]

第3轮

上个结果，只有一组元素 [2,3 ]，进行排序

选择 最后元素 3 作为中心基准元素，与各个元素比较，小的放前，大的放后，结果：

从前往后循环（ 3 除外，因为是基准元素）：

  • 第1个元素 2，比 3 小，此时不动

结果：

[2,3]

整个序列是：[1, 2, 3, 4, 9, 8, 11, 5, 10, 8, 12, 8, 7, 6, ]

第4轮

对 第一轮 结果的 第二组元素 [9, 8, 11, 5, 10, 8, 12, 8, 7, 6, ] 进行排序

过程同上，略

第9轮

[1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10, 11, 12 ]

时间复杂度

O(n\log_2n)

计算过程

有上面例子可知：

数组长度 n=14，每次平分：

  • 第 0 层（原始数组）：长度 14 → 分区耗时 O (14)
  • 第 1 层（两个子数组）：长度 3+10 → 分区总耗时 O (3)+O (10)，大O表示法为 O(14) （忽略常数、系数等）
  • 第 2 层（四个子数组）：分区总耗时 O (14)
  • 第 3 层（八个子数组）：分区总耗时 O (14)

层数：\log_214，每层都执行 14 次，所以 时间复杂度：n\log_2n

最差的情况

原本就基本有序，此时选取 第一个元素作为中心点，没有分成两组，一直是一组

解决：选取处于 中位数 的元素作为中心点

空间复杂度

辅助空间

  • 空间复杂度默认为 O(1)
  • 需要辅助空间存储左侧数组和右侧数组时，空间复杂度为O(n)
  • 需要记录所有基准元素时，空间复杂度为 O(log₂n)

算法稳定性

不稳定，任意选取中心点，然后与各个元素比较

实现

public class 快速排序2 {
    static int r = 1;
    public static void main(String[] args) {
        // 测试数组（包含重复元素，可验证排序逻辑）
        int[] arr = {6, 3, 8, 2, 9, 1, 11, 5, 10, 8, 12, 8, 7, 4};
        System.out.println("排序前数组：");
        printArray(arr);

        // 快速排序入口：左边界0，右边界数组长度-1
        quickSort(arr, 0, arr.length - 1);

        System.out.println("\n排序后数组（升序）：");
        printArray(arr);
    }

    /**
     * 快速排序递归方法
     * @param arr 待排序数组
     * @param left 子数组左边界
     * @param right 子数组右边界
     */
    public static void quickSort(int[] arr, int left, int right) {
        // 递归终止条件：子数组长度≤1（天然有序）
        if (left >= right) {
            return;
        }

        // 划分区间：返回基准值的最终位置
        int pivotIndex = partition(arr, left, right);

        // 递归排序左子数组（基准左侧）
        quickSort(arr, left, pivotIndex - 1);
        // 递归排序右子数组（基准右侧）
        quickSort(arr, pivotIndex + 1, right);
    }

    /**
     * 划分区间核心方法（选最后一个元素为基准）
     * @param arr 待划分数组
     * @param low 左边界
     * @param high 右边界（基准值所在位置）
     * @return 基准值的最终位置
     */
    public static int partition(int[] arr, int low, int high) {
        System.out.println("第"+r+"轮开始--------");
        // 1. 选最后一个元素作为基准值
        int pivot = arr[high];
        System.out.print("--对部分数组进行排序：");
        printArray(arr,low,high);
        System.out.println("基准元素："+pivot);
        // 1. 选最后一个元素作为基准值（挖坑：把基准值暂存，high位置变成"坑"）
        int i = low; // 单指针：从左边界开始，标记"小于基准值"区域的右边界

        // 2. 遍历low到high-1的所有元素（避开基准值）
        for (int j = low; j < high; j++) {
            // 3. 找到小于等于基准值的元素，放到"小于区域"的下一个位置
            if (arr[j] <= pivot) {
                // 交换i和j位置的元素
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                // 扩大"小于基准值"的区域
                i++;
                System.out.print("----交互位置：");
                printArray(arr,low,high);
            }
        }

        // 4. 把基准值填入最终的坑位（i的位置）
        arr[high] = arr[i];
        arr[i] = pivot;

        System.out.print("--对部分数组进行排序的结果：");
        printArray(arr,low,high);
        System.out.print("第"+r+"轮结果：");
        printArray(arr);
        r++;
        // 返回基准值的最终下标
        return i;
    }

    /**
     * 交换数组中两个元素的位置
     * @param arr 数组
     * @param a 下标a
     * @param b 下标b
     */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


    // 辅助方法：打印数组元素，方便查看排序前后结果
    private static void printArray(int[] arr) {
        System.out.print("[");
        for (int num : arr) {
            System.out.print(num + ", ");
        }
        System.out.print("]");
        System.out.println();
    }

    private static void printArray(int[] arr,int left,int right) {
        System.out.print("[");
        for (int i = left;i<=right;i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.print("]");
        System.out.println();
    }

}

题

对数组 A=(2,8,7,1,3,5,6,4) 用快速排序算法的划分方法进行一趟划分后得到的数组A为（ ）(非递减排序，以最后一个元素为基准元素）。进行一趟划分的计算时间为( )

A、(1,2,8,7,3,5,6,4) B、(1,2,3,4,8,7,5,6)
C、(2,3,1,4,7,5,6,8) D、(2,1,3,4,8,7,5,6)

A、O(1) B、O(lgn)
C、O(n) D、O(nlgn)

第1问-分析

  • 非递减排序，也就是递增排序，执行第一趟后，最后一个元素是最大值，所以最后一个元素是 8，所以排除 ABD

  • 最后一个元素为基准元素：所以 4 是基准元素，第一个元素 2 比 4 小，不动，所以第一趟执行后，第一个元素还是 2

第2问-分析

基准元素要与其他 n-1 个元素比较，所以执行 n-1 次，渐进法表示时间复杂度：O(n)

第1问-答案

C

第2问-答案

C

原文出处：/show_1GW2hUYDeP9H.html

吉ICP备15003043号