快速排序（Quick Sort）是一种常用的排序算法，采用分治法（Divide and Conquer）进行排序。其基本思路是通过选择一个基准元素（pivot），将待排序的数组分成两部分，一部分所有元素都小于基准元素，另一部分所有元素都大于基准元素。然后递归地对这两部分继续进行排序，最终达到排序整个数组的效果。
快速排序的步骤：
- 选择基准元素：选择数组中的一个元素作为基准元素（常见的选择有第一个元素、最后一个元素、随机选择等）。
- 分区操作：将数组分成两部分，小于基准的放左边，大于基准的放右边。基准元素最终的位置已经确定。
- 递归排序：对基准元素左侧和右侧的子数组进行递归调用快速排序，直到子数组的大小为1或0，排序完成。
时间复杂度：
- 最佳情况：
O(n log n)，发生在每次分割时都能平衡地分成两部分。 - 最坏情况：
O(n^2)，当数组已经有序或反向有序时，每次选择的基准元素都可能是最小或最大的元素，从而导致不均匀的分割。 - 平均情况：
O(n log n)，在大多数情况下，快速排序的时间复杂度表现良好。
空间复杂度：
- 快速排序是原地排序，只需要
O(log n) 的栈空间来存储递归调用的状态。 - 空间复杂度主要取决于递归的深度，最坏情况下是
O(n)，但平均情况下是 O(log n)。
快速排序的Java实现代码：
public class QuickSort {
// 主函数：调用快速排序
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSortHelper(arr, 0, arr.length - 1);
}
// 快速排序的核心递归函数
private static void quickSortHelper(int[] arr, int left, int right) {
if (left < right) {
// 分区操作，返回基准元素的正确位置
int pivotIndex = partition(arr, left, right);
// 递归对基准元素左侧和右侧的子数组排序
quickSortHelper(arr, left, pivotIndex - 1);
quickSortHelper(arr, pivotIndex + 1, right);
}
}
// 分区操作，返回基准元素的最终位置
private static int partition(int[] arr, int left, int right) {
// 选择最右边的元素作为基准元素
int pivot = arr[right];
int i = left - 1; // i 指向比基准小的元素区域的最后一个元素
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
// 交换 arr[i + 1] 和 arr[j]
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 = {3, 6, 8, 10, 1, 2, 1};
System.out.println("Original array: ");
printArray(arr);
quickSort(arr);
System.out.println("Sorted array: ");
printArray(arr);
}
// 打印数组的辅助函数
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
代码解析：
- quickSort：是快速排序的入口方法，接收一个数组作为参数，检查数组是否为空或大小小于2，若满足条件则无需排序，直接返回。
- quickSortHelper：是一个递归函数，通过分区操作将数组划分为左右两部分，然后递归地对这两部分继续排序。
- partition：分区操作方法，它选择数组的最后一个元素作为基准元素，并通过两端的指针进行交换，将小于基准的元素放到左边，大于基准的元素放到右边。最终，基准元素被放到正确位置并返回其索引。
- swap：交换数组中两个元素的辅助函数。
- printArray：打印数组内容的辅助函数。
复杂度分析：
- 时间复杂度：
- 最佳情况：
O(n log n)，当每次分区都能将数组平衡地分成两部分。 - 最坏情况：
O(n^2)，当每次分区都选到数组的极端元素（如最小或最大），导致每次只能减少一个元素的排序，递归的深度为 n。 - 平均情况：
O(n log n)，是快速排序最常见的表现。
- 空间复杂度：
- 最好和平均情况下：
O(log n)，由于递归的深度受限于树的高度。 - 最坏情况下：
O(n)，当数组已经是排序好的，或者每次选到的基准元素极端时，递归的深度为 n。