mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4mobile wallpaper 5mobile wallpaper 6
Profile Image of the Author
黎明
公告
欢迎来到黎明的小站。本站用于堆叠平时的技术痕迹，记录一些值得留存的想法。
标签
1168 字
3 分钟
快速排序
2026-06-09 03:29:38
Algorithm
Algorithm
/
快速排序
/
分治法
/
双指针

1. 问题引入#

快速排序的核心步骤是 partition 划分：选一个基准元素 pivot，把数组分成两边，使得左边元素都不大于它，右边元素都不小于它。

例如数组 6 3 8 2 7 5，如果以 6 作为基准值，第一次划分后可能变成：

5 3 2 6 7 8

这时 6 已经落到了最终位置，但左右两边还没有完全有序。

2. 算法策略#

快速排序使用的是分治法：

分解：通过 partition 把数组划分成左右两个子数组 解决：分别递归排序左右两个子数组 合并：快速排序不需要额外合并

partition 的任务不是直接排好整个数组，而是先确定一个基准元素的最终位置。

3. partition 的基本思想#

这里使用一种常见写法：挖坑填数法。

过程很简单：

  1. 选择第一个元素作为 pivot 并暂存。
  2. 从右往左找小于 pivot 的数，填到左边的坑。
  3. 从左往右找大于 pivot 的数，填到右边的坑。
  4. 重复以上过程，直到左右指针相遇。
  5. 把 pivot 放回相遇位置。

快速排序挖坑过程

4. Java 实现#

public class QuickSortPartition {


    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left;
        int j = right;


        while (i < j) {
            // 从右往左找第一个小于 pivot 的元素
            while (i < j && arr[j] >= pivot) {
                j--;
            }


            // 把右边找到的小元素填到左边的坑
            arr[i] = arr[j];


            // 从左往右找第一个大于 pivot 的元素
            while (i < j && arr[i] <= pivot) {
                i++;
            }


            // 把左边找到的大元素填到右边的坑
            arr[j] = arr[i];
        }


        // 左右指针相遇，把 pivot 放回最终位置
        arr[i] = pivot;


        return i;
    }


    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 7, 5};


        int pivotIndex = partition(arr, 0, arr.length - 1);


        System.out.println("pivot 最终位置：" + pivotIndex);


        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

输出结果：

pivot 最终位置：3
5 3 2 6 7 8

5. 执行过程分析#

下面用数组：

6 3 8 2 7 5

演示一次 partition。

选择第一个元素作为基准值：

pivot = 6

初始状态如下：

[6, 3, 8, 2, 7, 5]
 i              j

其中：

i = 0
j = 5
pivot = 6

6. 第一次右扫描#

代码先执行：

while (i < j && arr[j] >= pivot) {
    j--;
}

从右往左找第一个小于 6 的元素。

此时：

arr[5] = 5

因为：

5<65 < 6

所以右扫描停止。

把 5 填到左边的坑：

arr[i] = arr[j];

数组变为：

[5, 3, 8, 2, 7, 5]
 i              j

左边的坑被填上了，右边位置 j 变成新的坑。

7. 第一次左扫描#

接着执行：

while (i < j && arr[i] <= pivot) {
    i++;
}

从左往右找第一个大于 6 的元素。

扫描过程：

arr[0] = 5 <= 6，i 右移
arr[1] = 3 <= 6，i 右移
arr[2] = 8 > 6，停止

此时：

[5, 3, 8, 2, 7, 5]
       i        j

把 8 填到右边的坑：

arr[j] = arr[i];

数组变为：

[5, 3, 8, 2, 7, 8]
       i        j

右边的坑被填上了，左边位置 i 变成新的坑。

8. 第二次右扫描#

继续从右往左找小于 6 的元素。

当前：

[5, 3, 8, 2, 7, 8]
       i        j

扫描过程：

arr[5] = 8 >= 6，j 左移
arr[4] = 7 >= 6，j 左移
arr[3] = 2 < 6，停止

此时：

[5, 3, 8, 2, 7, 8]
       i  j

把 2 填到左边的坑：

arr[i] = arr[j];

数组变为：

[5, 3, 2, 2, 7, 8]
       i  j

这里出现两个 2 并不是错误，因为 pivot = 6 已经被单独保存起来了，数组只是不断在填坑，最后会把 pivot 放回去。

9. 第二次左扫描#

继续从左往右找大于 6 的元素。

当前：

[5, 3, 2, 2, 7, 8]
       i  j

扫描过程：

arr[2] = 2 <= 6，i 右移

此时：

i == j

左右指针相遇，循环结束。

把 pivot 放到相遇位置：

arr[i] = pivot;

数组变为：

[5, 3, 2, 6, 7, 8]
          i

返回下标：

3

10. partition 结束后的含义#

最终结果：

5 3 2 6 7 8

可以看成：

5 3 2 | 6 | 7 8

其中：

6 左边的元素都 <= 6
6 右边的元素都 >= 6
6 的最终位置已经确定

但左边的 5 3 2 还没有完全有序，所以快速排序还要继续递归处理左右两边。

11. 完整快速排序 Java 代码#

public class QuickSort {


    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }


        int pivotIndex = partition(arr, left, right);


        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }


    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left;
        int j = right;


        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }


            arr[i] = arr[j];


            while (i < j && arr[i] <= pivot) {
                i++;
            }


            arr[j] = arr[i];
        }


        arr[i] = pivot;


        return i;
    }


    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 7, 5};


        quickSort(arr, 0, arr.length - 1);


        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

输出结果：

2 3 5 6 7 8

12. 复杂度分析#

12.1 单次 partition 的复杂度#

一次 partition 中，左右指针整体只会从两端向中间移动一遍。

所以单次 partition 的时间复杂度为：

O(n)O(n)

空间复杂度为：

O(1)O(1)

12.2 快速排序整体复杂度#

快速排序的复杂度取决于每次划分是否均衡。

如果每次都能把数组大致分成两半，那么时间复杂度为：

O(nlog⁡n)O(n \log n)

如果每次选到的 pivot 都是最大值或最小值，那么划分会很不均衡，时间复杂度会退化为：

O(n2)O(n^2)

常见情况如下：

情况时间复杂度
最好情况O(nlog⁡n)O(n \log n)
平均情况O(nlog⁡n)O(n \log n)
最坏情况O(n2)O(n^2)

13. 常见优化#

如果数组本身接近有序，而每次都选择第一个元素作为 pivot，快速排序很容易退化。

常见优化方法有：

  1. 随机选择 pivot
  2. 三数取中选择 pivot
  3. 小区间改用插入排序

其中随机选择 pivot 可以降低每次都选到极端值的概率。

14. 总结#

快速排序 partition 划分可以概括为：

选基准，左右扫；小的填左边，大的填右边；指针相遇，基准归位。

核心内容如下：

  • partition 是快速排序的核心操作。
  • 通常选择一个元素作为 pivot。
  • 左右指针不是同时扫描，而是交替扫描。
  • 挖坑填数法会先从右往左找小元素，再从左往右找大元素。
  • partition 结束后，pivot 的位置已经确定。
  • partition 结束后，左右两边不一定完全有序。
  • 快速排序继续递归处理左右子数组。
  • 单次 partition 时间复杂度是 O(n)O(n)。
  • 快速排序平均时间复杂度是 O(nlog⁡n)O(n \log n)，最坏是 O(n2)O(n^2)。
分享

如果这篇文章对你有帮助，欢迎分享给更多人！

快速排序
https://dawn114514.site/posts/algorithm/quikesort/
作者
黎明
发布于
2026-06-09 03:29:38
许可协议
MIT

部分信息可能已经过时

归并排序
素数环问题（回溯法）
相关文章 智能推荐
1
快速幂
Algorithm 通过迭代（二进制角度）与递归（分治法角度）两种方法详细解析快速幂算法，解决数值的整数次幂问题，并将时间复杂度优化至 O(log n)。
2
归并排序
Algorithm 归并排序采用经典的分治策略，将序列分解为子序列进行排序，再合并为完全有序的序列。
3
第二大元素问题
Algorithm 从两种题型出发，介绍一次遍历和分治两种解法，重点讲清分治合并时的候选淘汰思想。
4
堆排序
Algorithm 堆排序利用完全二叉树结构的大根堆或小根堆性质，通过建堆与交替调整实现原地升序或降序排列。
5
0-1 背包问题（动态规划、回溯法、分支限界法）
Algorithm 从决策树到分支限界，三种视角求解 0-1 背包：动态规划求最优值，回溯法与分支限界用上界剪枝。
随机文章 随机推荐
1
蒙特卡罗算法：用随机撒点估算圆周率
Algorithm 2026-06-10
2
数据结构：最小栈
Algorithm 2026-05-13
3
0-1 背包问题（动态规划、回溯法、分支限界法）
Algorithm 2026-06-16
4
链表：合并两个有序链表
Algorithm 2026-05-11
5
快速幂
Algorithm 2026-06-10
豫ICP备2026007336号 萌ICP备20266900号
© 2026 黎明. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录