排序-快速排序
快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家霍尔（C. A. R. Hoare）在1960年提出。它的基本思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。以下是快速排序的主要知识点：
-
基本思想：
- 选择一个基准元素（pivot）。
- 通过一趟排序将待排序列分割成独立的两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大。
- 然后对这两部分分别进行快速排序，整个排序过程可以递归进行。
-
选择基准元素：
- 基准元素的选择有多种方法，如选择序列的第一个、最后一个或中间元素作为基准。
- 基准元素的选择对快速排序的性能有很大影响，因此有些优化版本的快速排序会采用更复杂的策略来选择基准元素。
-
分割过程：
- 从序列的右端开始，向左扫描，找到第一个小于基准元素的元素。
- 从序列的左端开始，向右扫描，找到第一个大于基准元素的元素。
- 交换这两个元素的位置。
- 重复以上步骤，直到左、右指针相遇或交错。
-
递归排序：
- 对基准元素左边的子序列和右边的子序列分别进行快速排序。
-
优化策略：
- 三数取中法：选择序列首、尾、中间三个数中的中值作为基准元素，以减少最坏情况（O(n^2)）的发生概率。
- 小数组直接插入排序：当子序列的长度较小时，直接采用插入排序而不是递归调用快速排序，因为插入排序在处理小数组时效率更高。
- 处理相等元素：在分割过程中，当遇到与基准元素相等的元素时，可以将其与基准元素交换到同一侧，以减少不必要的交换和比较。
-
时间复杂度：
- 平均时间复杂度：O(nlogn)，其中n是待排序列的长度。
- 最坏时间复杂度：O(n2)，当输入序列已经有序或接近有序时，快速排序的性能会退化为O(n2)。
- 最好时间复杂度：O(nlogn)，当每次分割都能将序列均匀地分成两部分时，快速排序的性能最好。
-
空间复杂度：
- 快速排序是原地排序算法，空间复杂度为O(logn)，其中logn是递归调用栈的最大深度。但在最坏情况下，递归调用栈的深度可能达到n，因此空间复杂度为O(n)。然而，这种情况在实际应用中很少出现。
-
稳定性：
- 快速排序是不稳定的排序算法，因为在分割过程中可能会改变相等元素的相对顺序。
-
代码示例：
public class QuickSort { public static void quickSort(int[] array, int left, int right) { if (left < right) { int pivotIndex = partition(array, left, right); quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex + 1, right); } } private static int partition(int[] array, int left, int right) { int pivot = array[right]; // 通常选择最右侧的元素作为基准 int i = left - 1; // i为小于基准元素的索引 for (int j = left; j <= right - 1; j++) { if (array[j] <= pivot) { i++; // 交换array[i]和array[j] int temp = array[i]; array[i] = array[j]; array[j] = temp; } } // 将基准元素放到正确的位置 int temp = array[i + 1]; array[i + 1] = array[right]; array[right] = temp; // 返回基准元素的索引 return i + 1; } public static void main(String[] args) { int[] array = {3, 6, 8, 10, 1, 2, 1}; quickSort(array, 0, array.length - 1); // 打印排序后的数组 for (int num : array) { System.out.print(num + " "); } }
}在这个实现中，quickSort 方法是递归的主体部分，它调用 partition 方法来选择一个基准元素，并将数组分为两部分。partition 方法负责选择基准元素（这里选择的是最右侧的元素），并重新排列数组，使得小于基准的元素都在其左边，大于基准的元素都在其右边。然后，quickSort 方法递归地对基准元素左右两边的子数组进行排序。
在 main 方法中，我们创建了一个需要排序的数组，并调用了 quickSort 方法。最后，我们打印出排序后的数组。
注意，这个实现假设输入的数组 array 不会被其他线程修改，并且在排序过程中不会改变原数组（因为它是在原数组上进行原地排序的）。