详解快速排序
引言
快速排序（QuickSort）是一种分而治之的排序算法。它通过选择一个基准元素，将数组分为两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分再进行快速排序，最终得到有序的数组。
算法思想
-
选择基准值（Pivot Selection）：从数组中挑选一个元素作为基准值（Pivot）。基准值的选择方式多样，例如选择首个元素、末尾元素、中间元素或随机元素。
-
分区操作（Partitioning）：重新排列数组，让所有小于基准值的元素位于基准值的左侧，所有大于基准值的元素位于基准值的右侧。这个过程被称作分区（Partition）。分区结束后，基准值就处于其最终排序后的位置。
-
递归排序（Recursive Sorting）：分别对基准值左右两侧的子数组递归地应用上述两个步骤，直至子数组的大小为 0 或者 1，此时数组已完全有序。
算法分析
时间复杂度
-
最优情况：当每次选择的基准元素正好将数组分成两等分时，快速排序的时间复杂度是O(nlogn)
-
最坏情况：当每次选择的基准元素是最大或最小元素时，快速排序的时间复杂度是O(n^2)。
-
平均情况：在平均情况下，快速排序的时间复杂度也是O(nlogn)
空间复杂度
快速排序的空间复杂度是O(logn)，因为在递归调用中需要使用栈来存储中间结果。这意味着
在排序过程中，最多需要O(logn)的额外空间来保存递归调用的栈帧。
优化方案
-
选择合适的基准：选择合适的基准元素可以提高算法的性能。
-
三数取中;通过选择中间元素作为基准，可以避免最坏情况的出现。
-
分区的改进：可以使用双指针或其他方法来改进分区的过程，提高算法的效率。
-
小数组使用插入排序：对于小数组，可以直接使用插入排序，避免不必要的递归。
Java实现
/*** 交换数组中两个指定位置的元素* @param nums 待操作的数组* @param i 第一个元素的索引* @param j 第二个元素的索引*/
public void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;
}/*** 快速排序的分区函数，选择一个基准值并将数组分为两部分* 左边部分元素都小于等于基准值，右边部分元素都大于等于基准值* @param nums 待分区的数组* @param l 左边界索引* @param r 右边界索引* @return 基准值最终所在的索引位置*/
public int partition(int nums[], int l, int r) {// 随机选择一个索引作为基准值的位置，减少最坏情况的发生概率Random random = new Random();int index = l + random.nextInt(r - l + 1);// 将基准值交换到数组的左边界位置swap(nums, l, index);int i = l; // 左指针，从左边界开始int j = r; // 右指针，从右边界开始int x = nums[i]; // 基准值，此时位于左边界位置// 双指针扫描，将数组分为两部分while (i < j) {// 从右向左找第一个小于等于基准值的元素while (i < j && nums[j] > x) {j--;}// 将找到的元素交换到左边if (i < j) {swap(nums, i, j);i++; // 左指针右移一位}// 从左向右找第一个大于等于基准值的元素while (i < j && nums[i] < x) {i++;}// 将找到的元素交换到右边if (i < j) {swap(nums, i, j);j--; // 右指针左移一位}}// 返回基准值最终所在的位置return i;
}/*** 快速排序主函数，递归地对数组进行排序* @param nums 待排序的数组* @param l 左边界索引* @param r 右边界索引*/
public void quickSort(int nums[], int l, int r) {// 递归终止条件：当左边界大于右边界时，区间内没有元素或只有一个元素，已经有序if (l >= r) {return;}// 分区并获取基准值的位置int pivot = partition(nums, l, r);// 递归排序基准值左边的子数组quickSort(nums, l, pivot - 1);// 递归排序基准值右边的子数组quickSort(nums, pivot + 1, r);
}