排序算法之快速排序详细解读（附带Java代码解读）

本文主要是介绍排序算法之快速排序详细解读（附带Java代码解读），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快速排序（Quick Sort）是一种高效的排序算法，由 C.A.R. Hoare 在 1960 年提出。它采用分治法的思想，将数组分为两部分，然后分别对这两部分进行排序，最终合并成一个有序数组。快速排序在大多数情况下表现优异，通常被认为是排序算法中最快的之一。

算法思想

选择基准：从数组中选择一个元素作为基准（pivot）。
分区：将数组中的元素重新排列，使得比基准小的元素在基准的左边，比基准大的元素在基准的右边。
递归排序：递归地对基准左边和右边的子数组进行快速排序。

过程示例

假设有一个待排序的数组：[10, 7, 8, 9, 1, 5]

步骤 1: 选择基准：

选择数组的最后一个元素 5 作为基准。

步骤 2: 分区：

对数组进行分区，使得所有小于基准的元素在左边，大于基准的元素在右边。

初始数组：[10, 7, 8, 9, 1, 5]
比较 10 与 5，10 > 5，移动指针。
比较 7 与 5，7 > 5，移动指针。
比较 8 与 5，8 > 5，移动指针。
比较 9 与 5，9 > 5，移动指针。
比较 1 与 5，1 < 5，将 1 交换到左边。

最终数组变为：[1, 7, 8, 9, 10, 5]

将基准 5 放到它的正确位置，数组变为：[1, 5, 8, 9, 10, 7]

步骤 3: 递归排序：

对基准左边的子数组 [1] 和右边的子数组 [8, 9, 10, 7] 进行递归排序。

左边子数组 [1] 已经有序。
右边子数组 [8, 9, 10, 7] 的快速排序过程：
- 选择基准 7，将其放到合适位置，分区后得到 [7, 8, 9, 10]。
- 左边子数组 [8, 9, 10] 进行快速排序：
  - 选择基准 10，无需交换，最终有序。

最终得到有序数组：[1, 5, 7, 8, 9, 10]

算法复杂度

时间复杂度:
- 最坏情况: O(n^2)（当选择的基准是数组中的最大或最小元素时）
- 平均情况: O(n log n)
- 最佳情况: O(n log n)（当基准每次都能将数组均匀分割时）
空间复杂度: O(log n) 快速排序的空间复杂度取决于递归调用栈的深度，通常为 O(log n)。

优点

效率高：快速排序在大多数情况下比其他 O(n log n) 算法（如归并排序和堆排序）更快。
原地排序：不需要额外的存储空间，适合内存有限的情况。
排序稳定性：虽然标准的快速排序是不稳定的，但可以通过修改算法使其稳定。

缺点

最坏情况性能差：在最坏情况下，时间复杂度为 O(n^2)，例如当数组已经排好序时。
不稳定排序：标准实现的快速排序是不稳定的，可能会改变相同元素的相对位置。

Java代码解读

public class QuickSort {// 快速排序方法public static void quickSort(int[] arr, int low, int high) {if (low < high) {// 找到基准元素的正确位置int pi = partition(arr, low, high);// 递归排序基准左边和右边的子数组quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}// 分区方法private static int partition(int[] arr, int low, int high) {int pivot = arr[high];  // 选择基准元素int i = (low - 1);  // 记录较小元素的索引for (int j = low; j < high; j++) {// 如果当前元素小于基准元素if (arr[j] < pivot) {i++;  // 增加较小元素的索引// 交换当前元素与较小元素索引对应的元素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;  // 返回基准元素的索引}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};System.out.println("排序前的数组:");for (int num : arr) {System.out.print(num + " ");}System.out.println();quickSort(arr, 0, arr.length - 1);System.out.println("排序后的数组:");for (int num : arr) {System.out.print(num + " ");}}
}

代码说明

quickSort方法:
- low 和 high 分别表示当前排序的子数组的起始和结束索引。
- 调用 partition 方法找到基准元素的正确位置 pi，然后递归地对基准左边和右边的子数组进行排序。
partition方法:
- 选择数组的最后一个元素作为基准。
- 遍历数组，将小于基准的元素移到基准的左边，大于基准的元素留在右边。
- 将基准元素放到正确的位置，返回基准的索引。
main方法:
- 创建一个待排序的数组 arr。
- 调用 quickSort 方法对数组进行排序。
- 输出排序前和排序后的数组。