快速排序算法

一、快速排序简介

**快速排序（Quick Sort）**是一种基于分治法的高效排序算法，由C. A. R. Hoare于1960年提出。它的平均时间复杂度为O(n log n)，在实际应用中，由于其优秀的性能和较高的效率，被认为是排序算法中的佼佼者。

二、算法思想

快速排序的核心思想是：

选择主元（Pivot）：从待排序序列中选择一个基准元素，称为主元。
分区操作：将序列划分为两个子序列，使得左子序列中所有元素都小于主元，右子序列中所有元素都大于或等于主元。
递归排序：对左右子序列分别递归地进行快速排序。

三、算法步骤

初始序列：给定一个待排序的数组或序列。
选择主元：通常选择序列的第一个、最后一个、中间位置或随机位置的元素作为主元。
分区（Partition）：
- 设置两个指针，分别指向序列的起始位置和结束位置。
- 从左到右移动左指针，找到第一个大于等于主元的元素。
- 从右到左移动右指针，找到第一个小于等于主元的元素。
- 交换左、右指针所指向的元素。
- 重复上述过程，直到左指针超过右指针。
交换主元：将主元放到正确的位置（通常是右指针所在的位置）。
递归调用：对主元左右两侧的子序列重复上述过程，直到序列有序。

四、算法实现

以下是快速排序的Java实现：

java">public class QuickSortExample {public static void quickSort(int[] arr, int left, int right) {if (left < right) {// 分区操作，返回主元的位置int pivotIndex = partition(arr, left, right);// 对左子序列进行快速排序quickSort(arr, left, pivotIndex - 1);// 对右子序列进行快速排序quickSort(arr, pivotIndex + 1, right);}}private static int partition(int[] arr, int left, int right) {// 选择最右边的元素作为主元int pivot = arr[right];int i = left - 1;for (int j = left; j < right; j++) {// 将小于主元的元素放到左边if (arr[j] <= pivot) {i++;swap(arr, i, j);}}// 将主元放到正确的位置swap(arr, i + 1, right);return i + 1; // 返回主元的位置}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 测试快速排序public static void main(String[] args) {int[] arr = { 9, 3, 7, 5, 6, 4, 8, 2 };quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}
}

运行结果：

[2, 3, 4, 5, 6, 7, 8, 9]

五、动画演示

为了更直观地理解快速排序，可以想象以下过程：

初始序列：[9, 3, 7, 5, 6, 4, 8, 2]
选择主元：选择2（最后一个元素）作为主元。
分区结果：经过分区，序列变为[2, 3, 7, 5, 6, 4, 8, 9]，2的位置确定。
递归排序：对左子序列[2]和右子序列[3, 7, 5, 6, 4, 8, 9]进行递归排序。

依此类推，最终序列有序。

六、性能分析

时间复杂度：
- 平均时间复杂度：O(n log n)
- 最坏时间复杂度：O(n²)，当每次选取的主元都是序列中的最大或最小值时，可能退化为冒泡排序。
空间复杂度：O(log n)，递归调用栈的深度。
特点：
- 不稳定排序：快速排序不是稳定的排序算法，可能改变相等元素的相对位置。
- 原地排序：不需要额外的辅助空间。

七、优化策略

三数取中：选择主元时，取左、中、右三个元素的中间值，减少最坏情况出现的概率。
随机化主元：随机选择主元，避免序列有序导致的最坏情况。
尾递归优化：减少递归调用的深度，优化空间复杂度。
小规模优化：对于小规模的子序列，可以改用插入排序，提高效率。

八、力扣（LeetCode）相关题目

在LeetCode上，有多道题目涉及到快速排序或其应用。以下列举一些典型的题目：

1. 215. 数组中的第K个最大元素

题目描述：找到数组中第K大的元素。
解题思路：
- 快速选择算法（Quick Select）：快速排序的变种，只对一侧进行递归，效率更高。
- 实现：利用快速排序的分区思想，在分区后确定主元的位置与目标位置的关系，决定递归方向。

示例代码：

java">class Solution {public int findKthLargest(int[] nums, int k) {return quickSelect(nums, 0, nums.length - 1, nums.length - k);}private int quickSelect(int[] nums, int left, int right, int index) {int pivotIndex = partition(nums, left, right);if (pivotIndex == index) {return nums[pivotIndex];} else if (pivotIndex < index) {return quickSelect(nums, pivotIndex + 1, right, index);} else {return quickSelect(nums, left, pivotIndex - 1, index);}}private int partition(int[] nums, int left, int right) {int pivot = nums[right], i = left - 1;for (int j = left; j < right; j++) {if (nums[j] <= pivot) {swap(nums, ++i, j);}}swap(nums, ++i, right);return i;}private void swap(int[] nums, int i, int j) {int temp= nums[i];nums[i] = nums[j];nums[j] = temp;}
}

2. 912. 排序数组

题目描述：对数组进行排序。
解题思路：
- 经典快速排序：直接实现快速排序算法，对数组进行排序。

3. 973. 最接近原点的 K 个点

题目描述：在平面上找到离原点最近的K个点。
解题思路：
- 快速选择算法：利用快速选择找到距离最小的K个点。
- 实现：根据距离对点进行分区，类似于快速排序的思想。

4. 347. 前 K 个高频元素

题目描述：找到数组中出现频率最高的K个元素。
解题思路：
- 基于快速选择的优化：对频率进行排序，使用快速选择找到前K个高频元素。

5. 75. 颜色分类

题目描述：只有0、1、2三种颜色的数组，要求进行排序。
解题思路：
- 三路快排：快速排序的变种，将数组分为三部分，更高效地完成排序。

示例代码：

java">class Solution {public void sortColors(int[] nums) {int zero = -1, one = 0, two = nums.length;while (one < two) {if (nums[one] == 0) {swap(nums, ++zero, one++);} else if (nums[one] == 2) {swap(nums, one, --two);} else {one++;}}}private void swap(int[] nums, int i, int j) {int temp= nums[i];nums[i] = nums[j];nums[j] = temp;}
}