当前位置：首页 > news >正文

快速排序算法完整详解（原理+分步过程+代码+优化）

news 2026/7/9 8:53:20

本文目录如下：

一、快速排序基本思想

1、时间复杂度

2、空间复杂度

二、数组分步排序演示

第一轮分区（基准值 pivot = 3）

递归处理左右子区间

三、快速排序核心规律小结（适配快排特性）

四、基础版快速排序代码（单边递归+左右指针法）

五、快速排序优化方案（面试必考）

六、面试核心总结（对标冒泡笔记结尾）

一、快速排序基本思想

快速排序是交换排序的一种，基于分治、递归思想，是冒泡排序的优化升级版。

核心思路：在序列中选取一个基准值（pivot），通过一趟排序，将数组分区，比基准值小的放左边，比基准值大的放右边。完成分区后，基准值就位。再对左右两个子区间递归重复分区操作，最终实现整体有序。

特点：每一轮排序确定一个基准值的最终位置，不像冒泡一样逐轮固定末尾最大值。

1、时间复杂度

基础版快排（固定左端基准）

-最好情况（每次均分区间）：O(nlogn)

-最坏情况（有序/逆序数组）：O(n²)

-平均情况：O(nlogn)

优化版快排（随机/三数取中基准）

- 几乎杜绝最坏情况，日常稳定 O(nlogn)

- 平均、最好均为 O(nlogn)

2、空间复杂度

- 基础版、优化版：O(logn)~O(n)

- 解释：快排非原地排序（逻辑上原地），主要消耗递归栈空间；最优栈深度logn，最坏n

二、数组分步排序演示

待排序原始数组：3，9，-1，10，20

规则：默认选取最左侧元素为基准值，左指针找大值，右指针找小值，相遇交换，最终归位基准数。

第一轮分区（基准值 pivot = 3）

初始数组：【3，9，-1，10，20】

1、右指针先向左找小于3的数：找到 -1

2、左指针向右找大于3的数：找到 9

3、交换 9 和 -1 → 数组：【3，-1，9，10，20】

4、左右指针继续移动，最终相遇在索引1位置

5、将基准值 3 与相遇位置的值交换 → 【-1，3，9，10，20】

第一轮结果：基准值3已归位，左边全部小、右边全部大

递归处理左右子区间

左区间：[-1]，只有单个元素，天然有序，无需排序

右区间：[9,10,20]

对右区间重复选取基准、分区、递归操作：

1、以9为基准，分区后9归位，右侧剩余[10,20]

2、以10为基准，分区后10归位，剩余20天然有序

最终得到有序数组：[-1，3，9，10，20]

三、快速排序核心规律小结（适配快排特性）

1、快排不固定循环轮数，采用递归分治，不断划分子区间

2、每一次分区，仅确定基准值的最终位置

3、相较于冒泡每轮只能确定一个最值，快排一次分区可批量规整大量元素，效率极高

4、极端情况下（有序数组选最左为基准）会退化效率，需要针对性优化

四、基础版快速排序代码（单边递归+左右指针法）

public class QuickSort { public static void main(String[] args) { int[] arr = {3, 9, -1, 10, 20}; quickSort(arr, 0, arr.length - 1); // 输出结果 for (int num : arr) { System.out.print(num + " "); } } // 快排递归方法 public static void quickSort(int[] arr, int left, int right) { // 递归终止条件：区间只剩0/1个元素 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 l = left; int r = right; while (l < r) { // 右指针找比pivot小的 while (l < r && arr[r] >= pivot) { r--; } // 左指针找比pivot大的 while (l < r && arr[l] <= pivot) { l++; } // 交换左右指针元素 int temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; } // 指针相遇，基准值归位 arr[left] = arr[l]; arr[l] = pivot; return l; } }

五、快速排序优化方案（面试必考）

基础版缺陷：有序数组、逆序数组下，每次分区极不均衡，递归深度最大，算法退化严重，时间复杂度退化为 O(n²)。

优化方式：随机基准值 / 三数取中法，避免极端分区。

下面给出随机选取基准优化版（工程常用、面试首选）：

import java.util.Random; public class QuickSort { public static void main(String[] args) { int[] arr = {3, 9, -1, 10, 20}; quickSort(arr, 0, arr.length - 1); for (int num : arr) { System.out.print(num + " "); } } public static void quickSort(int[] arr, int left, int right) { if (left >= right) { return; } int pivotIndex = partitionRandom(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); } // 优化：随机选取基准 public static int partitionRandom(int[] arr, int left, int right) { // 随机下标 int randomIndex = new Random().nextInt(right - left + 1) + left; // 交换到最左，复用原有分区逻辑 int temp = arr[left]; arr[left] = arr[randomIndex]; arr[randomIndex] = temp; return partition(arr, left, right); } // 原有分区逻辑不变 public static int partition(int[] arr, int left, int right) { int pivot = arr[left]; int l = left; int r = right; while (l < r) { while (l < r && arr[r] >= pivot) r--; while (l < r && arr[l] <= pivot) l++; int temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; } arr[left] = arr[l]; arr[l] = pivot; return l; } }