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

# 介绍

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

### 中心元素（基准元素）

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

### 步骤

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

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

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

# 例子

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

### 第1趟

选择第一个元素 `6` 作为中心，与各个元素比较，小的放前，大的放后：

**第1次循环：**`6` 比 `3` 大，位置不变

**第2次循环：**`6` 比 `8` 小，比 `2` 大，所以交换 `8` 和 `2` 的位置，结果：
```
[6, 3, 2, 8, 9, 1, 11, 5, 10, 8, 12, 8, 7, 4, ]
```

**第3次循环：**`6` 比 `8` 小，比 `1` 大，所以交换 `8` 和 `1` 的位置，结果：
```
[6, 3, 2, 1, 9, 8, 11, 5, 10, 8, 12, 8, 7, 4, ]
```
**第4次循环：**`6` 比 `9` 小，比 `5` 大，所以交换 `9` 和 `5` 的位置，结果：
```
[6, 3, 2, 1, 5, 8, 11, 9, 10, 8, 12, 8, 7, 4, ]
```
**第5次循环：**`6` 比 `8` 小，比 `4` 大，所以交换 `8` 和 `4` 的位置，结果：
```
[6, 3, 2, 1, 5, 4, 11, 9, 10, 8, 12, 8, 7, 8, ]
```

**后面的循环：**由于后面的元素都比 `6` 大，所以都不执行

**最后：**`6` 比 `4` 大，所以交换 `6` 和 `4` 的位置，结果：

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

以 `6` 为中心点，分成两组元素：

- 比 `6` 小的
- 比 `6` 大的

### 第2趟 - 第4趟

对 **第一组元素** `[4, 3, 2, 1, 5,] ` 进行排序

选择第一个元素 `4` 作为中心，与各个元素比较，小的放前，大的放后

**前4次循环：**因为 `4` 比 `4,3,2,1`都大，所以位置不动

**最后一次循环：** 因为 `4` 比 `5` 小（后面没有元素了），终止循环

**最后：**由于 `4` 比 `5` 小，比 `1` 大，所以交换 `4` 和 `1` 的位置，结果：

```
[1, 3, 2, 4, 5,]
```

### 下一趟

同上，最终结果：`1, 3, 2, 4, 5,`

### 再下一趟

对 **第一组元素** `[11, 9, 10, 8, 12, 8, 7, 8] ` 进行排序

选择第一个元素 `11` 作为中心，与各个元素比较，小的放前，大的放后，最终结果：

```
7, 8, 8, 8, 9, 10, 11, 12,
```

### 最终

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

# 时间复杂度

```
O(nlog₂n)
```

### 最差的情况

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

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

# 空间复杂度

辅助空间

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

# 算法稳定性

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

# 实现

```
public class QuickSortFirstPivot {
    // 快排对外入口方法，仅传入待排序数组
    public static void quickSort(int[] arr) {
        // 边界判断：空数组/单元素数组无需排序，直接返回
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 递归处理整个数组，初始左边界0，右边界数组最后一位
        quickSortRecursion(arr, 0, arr.length - 1);
    }

// 递归排序方法：处理[left, right]区间的子数组
    private static void quickSortRecursion(int[] arr, int left, int right) {
        // 递归终止条件：左边界≥右边界，子数组长度≤1，天然有序
        if (left >= right) {
            return;
        }
        // 分区操作：以left为基准，返回基准值的最终索引
        int pivotIndex = partition(arr, left, right);
        // 递归处理左子数组：[left, pivotIndex-1]（都小于基准）
        quickSortRecursion(arr, left, pivotIndex - 1);
        // 递归处理右子数组：[pivotIndex+1, right]（都大于基准）
        quickSortRecursion(arr, pivotIndex + 1, right);
    }

// 核心分区方法：以left位置元素为基准，完成分区并返回基准最终索引
    // 单循环+双指针实现，简单易理解，适合新手
    private static int partition(int[] arr, int left, int right) {
        // 选左边界第一个元素作为基准值
        int pivot = arr[left];
        // mark指针：标记「小于等于基准值」的元素的最后一个位置
        // 初始为left（基准值本身占一个位置，后续遍历从left+1开始）
        int mark = left;

// 遍历区间[left+1, right]，寻找所有小于等于基准的元素
        for (int i = left + 1; i <= right; i++) {
            // 找到符合条件的元素，放到mark的下一个位置
            if (arr[i] <= pivot) {
                mark++; // mark右移，腾出存放位置
                swap(arr, mark, i); // 交换元素，归入左区
            }
        }

// 遍历结束，mark位置是左区最后一个元素，交换mark和left（基准原位置）
        // 此时基准值左侧全≤它，右侧全>它，基准归位
        swap(arr, mark, left);
        // 返回基准值的最终索引，供递归使用
        return mark;
    }

// 工具方法：交换数组中两个位置的元素，抽离后简化代码
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

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

// 主方法：测试用例，直接运行验证
    public static void main(String[] args) {
        // 待排序数组（和冒泡/之前快排用相同用例，方便对比）
        int[] arr = {6, 3, 8, 2, 9, 1};
        System.out.print("排序前的数组：");
        printArray(arr);

// 执行快速排序
        quickSort(arr);

System.out.print("排序后的数组：");
        printArray(arr);
    }
}
```

# 题

对数组 `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问-答案

### 第2问-答案

原文出处：http://www.malaoshi.top/show_1GW2hUYDeP9H.html