深入理解快速排序算法（Java实现）
1. 算法简介
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
2. 核心思想
快速排序使用分治法（Divide and Conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为 "基准"（pivot）;
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
3. Java 代码实现
下面是一个标准的快速排序实现：
import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] arr = {10, 7, 8, 9, 1, 5}; System.out.println("原始数组: " + Arrays.toString(arr)); quickSort(arr, 0, arr.length - 1); System.out.println("排序后数组: " + Arrays.toString(arr)); } /** * 快速排序主方法 * @param arr 待排序数组 * @param low 起始索引 * @param high 结束索引 */ public static void quickSort(int[] arr, int low, int high) { if (low < high) { // partitionIndex 是分区操作后 pivot 的位置 int partitionIndex = partition(arr, low, high); // 递归排序 pivot 左边和右边的元素 quickSort(arr, low, partitionIndex - 1); quickSort(arr, partitionIndex + 1, high); } } /** * 分区操作 * 该函数选取最后一个元素作为 pivot * 将小于 pivot 的元素放在 pivot 左边 * 将大于 pivot 的元素放在 pivot 右边 */ private static int partition(int[] arr, int low, int high) { // 选择最后一个元素作为基准 int pivot = arr[high]; // i 是较小元素的索引 int i = (low - 1); for (int j = low; j < high; j++) { // 如果当前元素小于或等于 pivot if (arr[j] <= pivot) { i++; // 交换 arr[i] 和 arr[j] swap(arr, i, j); } } // 交换 arr[i+1] 和 arr[high] (或 pivot) swap(arr, i + 1, high); return i + 1; } /** * 交换数组中的两个元素 */ private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }4. 复杂度分析
- 时间复杂度：
- 平均情况：O(n log n)
- 最坏情况：O(n^2) （例如数组已经有序，且每次选择最后一个元素作为基准）
- 最好情况：O(n log n)
- 空间复杂度：O(log n) （递归调用栈的空间）
快速排序通常被认为是同数量级（O(n log n)）的排序算法中平均性能最好的。
