快速排序
快速排序（Quick Sort）是由 C.A.R. Hoare 在 1960 年代提出的一种非常高效的排序算法。它采用分治法的思想，通过递归的方式将一个数组分成两个较小的子数组，然后分别对这两个子数组进行排序，最后将排序后的子数组合并起来形成完整的排序数组。快速排序在实际应用中非常广泛，特别是在大规模数据排序时表现优秀。
基本思想
快速排序的基本思想是选择一个基准元素（pivot），然后将数组分为两部分：
- 小于基准元素的部分：所有小于基准元素的元素。
- 大于基准元素的部分：所有大于基准元素的元素。
这个过程称为分区（partition），通过分区操作，基准元素最终位于其正确的位置，即在其左侧的元素都不大于它，在其右侧的元素都不小于它。然后递归地对左右两侧的子数组进行同样的操作，直到所有子数组的长度为 1 或 0。
代码实现
递归版本
查看代码
java
public class QuickSort {
// 分区操作
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++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i+1] 和 arr[high] (或基准)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// 返回基准元素的索引
return i + 1;
}
// 快速排序递归方法
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);
}
}
// 打印数组的方法
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
System.out.println("原始数组:");
printArray(arr);
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
printArray(arr);
}
}代码解释
- partition 方法：这个方法用于将数组分为两部分。它选择数组中的最后一个元素作为基准元素，并通过一次遍历将所有小于基准元素的值移到左边，大于基准元素的值移到右边。最后返回基准元素的正确索引。
- quickSort 方法：这是快速排序的核心递归方法。它首先调用
partition方法获得基准元素的索引，然后递归地对基准元素左侧和右侧的子数组进行排序。 - main 方法：测试快速排序的主程序入口。
迭代版本
迭代版本的快速排序使用一个栈来跟踪待排序的子数组的边界。每次分区后，将左右子数组的边界压入栈中，然后循环处理栈中的子数组，直到栈为空。
查看代码
java
public class IterativeQuickSort {
// 分区操作
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++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i+1] 和 arr[high] (或基准)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// 返回基准元素的索引
return i + 1;
}
// 迭代版本的快速排序
public static void quickSort(int[] arr) {
// 创建一个栈来存储子数组的边界
int[] stack = new int[arr.length];
int top = -1;
// 将初始的子数组边界压入栈
top++;
stack[top] = 0;
top++;
stack[top] = arr.length - 1;
// 不断从栈中弹出子数组的边界，并进行分区
while (top >= 0) {
// 弹出子数组的边界
int high = stack[top--];
int low = stack[top--];
// 分区
int pi = partition(arr, low, high);
// 如果左子数组不为空，将其边界压入栈
if (pi - 1 > low) {
top++;
stack[top] = low;
top++;
stack[top] = pi - 1;
}
// 如果右子数组不为空，将其边界压入栈
if (pi + 1 < high) {
top++;
stack[top] = pi + 1;
top++;
stack[top] = high;
}
}
}
// 打印数组的方法
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
System.out.println("原始数组:");
printArray(arr);
quickSort(arr);
System.out.println("排序后的数组:");
printArray(arr);
}
}代码解释
- partition 方法：这个方法与递归版本中的
partition方法相同，用于将数组分为两部分，并返回基准元素的索引。 - quickSort 方法：这是迭代版本的快速排序方法。它使用一个栈来跟踪待排序的子数组的边界。每次分区后，将左右子数组的边界压入栈中，然后循环处理栈中的子数组，直到栈为空。
- main 方法：测试迭代版本快速排序的主程序入口。
时间复杂度
- 最好情况：
- 平均情况：
- 最坏情况：
空间复杂度
快速排序的空间复杂度为
优化技巧
- 三数取中法：选择第一个元素、中间元素和最后一个元素的中位数作为基准元素，以减少最坏情况的发生。
- 随机选择基准：随机选择一个元素作为基准，以提高算法的平均性能。
- 尾递归优化：通过对递归调用进行优化，减少递归栈的深度。
- 小数组使用插入排序：对于小数组，使用插入排序代替快速排序，因为插入排序在小数组上的性能更好。