快速排序（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，无需交换，最终有序。
- 选择基准 7，将其放到合适位置，分区后得到
最终得到有序数组：[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方法对数组进行排序。 - 输出排序前和排序后的数组。
- 创建一个待排序的数组
