八大排序--快速排序

目录

什么是快速排序

步骤

举例

代码

---

什么是快速排序

        快速排序（Quick Sort）是一种高效的排序算法，基于分治法（Divide and Conquer）的思想。它的核心是通过选择一个基准元素（pivot），将列表分为两部分：一部分小于基准元素，另一部分大于基准元素，然后递归地对这两部分进行排序。快速排序的平均时间复杂度为 O(n log n)，在实际应用中性能优异。

步骤

        快速排序的核心是「分区」：选择一个元素作为「基准（pivot）」，把数组中比基准小的元素放到基准左边，比基准大的元素放到基准右边。然后对基准左右两边的子数组重复这个过程，直到子数组只有一个元素（无需排序）。

举例

我们以数组 [10, 7, 8, 9, 1, 5] 为例，一步步演示：

第 1 次调用：对整个数组排序（low=0，high=5）

• 选择基准：代码中选择最右边的元素作为基准，即 pivot = 5（索引 5 的元素）。
• 分区过程：目标是把比 5 小的元素放左边，比 5 大的放右边。
  • 初始状态：i = low - 1 = -1（i 是「小于基准区域」的边界），j 从 low=0 遍历到 high-1=4。
  • j=0 时，元素是 10：10 > 5 → 不交换，i 不变。
  • j=1 时，元素是 7：7 > 5 → 不交换，i 不变。
  • j=2 时，元素是 8：8 > 5 → 不交换，i 不变。
  • j=3 时，元素是 9：9 > 5 → 不交换，i 不变。
  • j=4 时，元素是 1：1 ≤ 5 → i 先 + 1（i=0），交换 i 和 j 的元素 → 数组变为 [1, 7, 8, 9, 10, 5]。
  • 遍历结束后，将基准元素放到「小于基准区域」的右边（i+1 的位置）：交换 i+1（索引 1）和 high（索引 5）的元素 → 数组变为 [1, 5, 8, 9, 10, 7]。
  • 此时基准 5 的位置是索引 1（记为 pi=1），左边子数组是 [1]（已排序），右边子数组是 [8, 9, 10, 7]（需要继续排序）。

第 2 次调用：对右边子数组 [8, 9, 10, 7] 排序（low=2，high=5）

• 选择基准：最右边的元素 7（索引 5 的元素）。
• 分区过程：
  • 初始 i = 2-1 = 1，j 从 2 遍历到 4。
  • j=2 时，元素是 8：8 > 7 → 不交换。
  • j=3 时，元素是 9：9 > 7 → 不交换。
  • j=4 时，元素是 10：10 > 7 → 不交换。
  • 遍历结束后，交换 i+1（索引 2）和 high（索引 5）的元素 → 数组变为 [1, 5, 7, 9, 10, 8]。
  • 基准 7 的位置是索引 2（pi=2），左边子数组已排序，右边子数组是 [9, 10, 8]（需要继续排序）。

第 3 次调用：对右边子数组 [9, 10, 8] 排序（low=3，high=5）

• 选择基准：最右边的元素 8（索引 5 的元素）。
• 分区过程：
  • 初始 i = 3-1 = 2，j 从 3 遍历到 4。
  • j=3 时，元素是 9：9 > 8 → 不交换。
  • j=4 时，元素是 10：10 > 8 → 不交换。
  • 遍历结束后，交换 i+1（索引 3）和 high（索引 5）的元素 → 数组变为 [1, 5, 7, 8, 10, 9]。
  • 基准 8 的位置是索引 3（pi=3），左边子数组已排序，右边子数组是 [10, 9]（需要继续排序）。

第 4 次调用：对右边子数组 [10, 9] 排序（low=4，high=5）

• 选择基准：最右边的元素 9（索引 5 的元素）。
• 分区过程：
  • 初始 i = 4-1 = 3，j 从 4 遍历到 4（只有一个元素）。
  • j=4 时，元素是 10：10 > 9 → 不交换。
  • 遍历结束后，交换 i+1（索引 4）和 high（索引 5）的元素 → 数组变为 [1, 5, 7, 8, 9, 10]。
  • 基准 9 的位置是索引 4（pi=4），右边子数组只有一个元素（10），无需排序。

最终结果

经过上述步骤，数组最终排序为 [1, 5, 7, 8, 9, 10]，整个过程通过不断「分区 - 递归」完成了排序。

代码

public class QuickSort {// 主方法，用于测试快速排序public static void main(String[] args) {// 测试数组int[] array = {10, 7, 8, 9, 1, 5};int n = array.length;System.out.println("排序前的数组:");printArray(array);// 调用快速排序方法quickSort(array, 0, n - 1);System.out.println("排序后的数组:");printArray(array);}// 快速排序主函数static void quickSort(int[] arr, int low, int high) {if (low < high) {// pi是分区索引，arr[pi]现在位于正确的位置int pi = partition(arr, low, high);// 分别对基准元素左右两边的子数组进行排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}// 分区操作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++) {// 如果当前元素小于或等于基准if (arr[j] <= pivot) {i++;// 交换arr[i]和arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将基准元素放到正确的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}// 打印数组static void printArray(int[] arr) {int n = arr.length;for (int value : arr) {System.out.print(value + " ");}System.out.println();}
}