Java快速排序实现思路

一、算法概述

该代码实现了 快速排序算法 ，核心思想是 采用分治策略 ：

0. 选择基准元素 ：从数组中选择一个元素作为基准（pivot）
1. 分区操作 ：将数组分为两部分，小于基准的元素放在左侧，大于基准的元素放在右侧
2. 递归排序 ：对左右两部分子数组分别递归执行上述过程
3. 合并结果 ：子数组排序完成后，整个数组自然有序

二、核心实现步骤

1. 主函数流程

public static void main(String[] args) {    int[] numbers = {13,4,6,1,10,9,12};    int[] newArray = quickSort(numbers, 0, numbers.length - 1);    for (int num: newArray) {        System.out.println(num);    }}

• 初始化 ：创建待排序数组 numbers
• 调用排序 ：调用 quickSort 方法，传入数组、起始索引和结束索引
• 结果输出 ：遍历排序后的数组，打印每个元素

2. 递归排序函数 quickSort

private static int[] quickSort(int[] arr, int left, int right) {    if (left < right) {        int partitionIndex = partition(arr, left, right);        quickSort(arr, left, partitionIndex - 1);        quickSort(arr, partitionIndex + 1, right);    }    return arr;}

• 递归终止条件 ： left >= right （子数组长度为0或1时已有序）
• 分区操作 ：调用 partition 方法获取基准元素的最终位置
• 递归调用 ：
• 左子数组： [left, partitionIndex-1] （小于基准的元素）
• 右子数组： [partitionIndex+1, right] （大于基准的元素）
• 返回结果 ：返回排序后的数组

3. 分区函数 partition

private static int partition(int[] arr, int left, int right) {    int pivot = left;  // 设定基准值    int index = pivot + 1;    for (int i = index; i <= right; i++) {        if (arr[i] < arr[pivot]) {            swap(arr, i, index);            index++;        }    }    swap(arr, pivot, index - 1);    return index - 1;}

• 基准选择 ：选择最左侧元素 arr[left] 作为基准
• 索引维护 ：
• pivot ：基准元素的初始位置
• index ：小于基准元素的区域边界（初始为 pivot+1 ）
• 遍历与交换 ：
• 从 index 遍历到 right ，比较每个元素与基准
• 若 arr[i] < arr[pivot] ，交换 arr[i] 和 arr[index] ， index++
• 最终 index 指向第一个大于基准的元素位置
• 基准定位 ：交换 pivot 和 index-1 ，将基准元素放到最终位置
• 返回值 ：返回基准元素的最终索引 index-1

4. 交换函数 swap

private static void swap(int[] arr, int i, int j) {    int temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}

• 辅助功能 ：交换数组中两个位置的元素
• 临时变量 ：使用 temp 保存交换过程中的中间值

三、排序过程示例（以 {13,4,6,1,10,9,12} 为例）

初始状态

数组：[13,4,6,1,10,9,12]范围：left=0, right=6

第一次分区（pivot=13，left=0，right=6）

0. index=1 ，遍历 i=1 到 6 ：
1. i=1 ： 4 < 13 → 交换 arr[1] 和 arr[1] → index=2
2. i=2 ： 6 < 13 → 交换 arr[2] 和 arr[2] → index=3
3. i=3 ： 1 < 13 → 交换 arr[3] 和 arr[3] → index=4
4. i=4 ： 10 < 13 → 交换 arr[4] 和 arr[4] → index=5
5. i=5 ： 9 < 13 → 交换 arr[5] 和 arr[5] → index=6
6. i=6 ： 12 < 13 → 交换 arr[6] 和 arr[6] → index=7
7. 交换 pivot(0) 和 index-1(6) → 数组变为 [12,4,6,1,10,9,13]
8. 分区点 partitionIndex=6
9. 递归处理左子数组 [0,5] ，右子数组 [7,6] （右子数组不处理）

左子数组 [0,5] 排序（省略详细步骤）

0. 分区后数组变为 [9,4,6,1,10,12,13] ，分区点=5
1. 左子数组 [0,4] 继续排序
2. 最终递归完成后，数组变为 [1,4,6,9,10,12,13]

四、算法特点

时间复杂度

• 最佳情况 ：O(nlogn)（每次分区均匀）
• 平均情况 ：O(nlogn)
• 最坏情况 ：O(n²)（数组已排序或逆序，分区极不均匀）

空间复杂度

• O(logn) ：递归调用栈的深度，平均情况为 logn
• 最坏情况 ：O(n)（递归深度达到n）

稳定性

• 不稳定排序 ：相同元素的相对位置可能改变

五、代码实现亮点

1. 清晰的分治结构

• 递归函数与分区函数分离，职责明确
• 代码结构清晰，易于理解和维护

2. 单边扫描分区法

• 从左到右遍历，维护一个索引边界
• 实现简单，效率较高
• 适合教学和理解快速排序的核心思想

3. 原地排序

• 不需要额外的数组空间
• 空间复杂度较低

4. 递归终止条件明确

• left < right 条件确保只有有效的子数组才会被处理
• 避免了无效的递归调用

六、代码优化方向

1. 基准选择优化

• 随机基准 ： int pivot = left + new Random().nextInt(right - left + 1)
• 三数取中法 ：选择左、中、右三个元素的中位数作为基准
• 避免最坏情况的发生

2. 处理重复元素

• 当数组中存在大量重复元素时，可采用 三路划分
• 将数组分为小于、等于、大于基准三部分
• 提高处理重复元素的效率

3. 小数据集优化

• 当子数组长度较小时（如小于10），切换为插入排序
• 减少递归调用开销，提高整体效率

4. 尾递归优化

• 将递归调用转换为迭代形式
• 减少栈空间的使用

七、总结

该代码实现了一个 标准的快速排序算法 ，通过分治策略将数组递归划分为更小的子数组进行排序。算法核心是分区操作，通过单边扫描法将数组分为小于和大于基准的两部分。代码结构清晰，易于理解，适合作为快速排序的教学示例。

快速排序是一种高效的排序算法，平均时间复杂度为O(nlogn)，空间复杂度为O(logn)，是实际应用中常用的排序算法之一。通过理解该实现的思路，可以深入掌握快速排序的核心原理和执行流程。