如何选好枢轴元素让快速排序避开最坏情况
一、快速排序算法初相识
快速排序是一种常用的排序算法，它的基本思想就是“分而治之”。打个比方，假如你要整理一堆杂乱无章的书籍，快速排序就像是先挑出一本作为“基准”，把比它薄的书放左边，比它厚的书放右边，然后再对左右两边的书分别重复这个过程，直到所有书都排好序。
下面是用 Java 实现的简单快速排序代码示例：
// Java 技术栈
public class QuickSort {
// 快速排序主方法
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 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++;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将枢轴元素放到正确的位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
在这个示例中，我们选择数组的最后一个元素作为枢轴元素。快速排序的平均时间复杂度是 $O(n log n)$，但在最坏情况下，时间复杂度会变成 $O(n^2)$。
二、最坏情况是怎么出现的
快速排序的最坏情况通常发生在枢轴元素选择不当时。比如，当数组已经是有序的（升序或降序），而我们每次都选择第一个或最后一个元素作为枢轴，就会导致划分极度不平衡。
假设我们有一个升序排列的数组 [1, 2, 3, 4, 5]，如果每次都选第一个元素 1 作为枢轴，那么第一次划分后，左边没有元素，右边有 [2, 3, 4, 5]。接着对右边的数组继续排序，每次划分都会出现类似的不平衡情况，这样就会让排序的效率变得很低，时间复杂度达到 $O(n^2)$。
三、选择合适枢轴元素的方法
随机选择枢轴
随机选择枢轴是一种简单有效的方法。就是在数组中随机选一个元素作为枢轴，这样可以避免在某些特定情况下出现最坏情况。
下面是随机选择枢轴的 Java 代码示例：
// Java 技术栈
import java.util.Random;
public class QuickSortRandomPivot {
// 快速排序主方法
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 int partition(int[] arr, int low, int high) {
// 随机选择一个索引作为枢轴
Random random = new Random();
int randomIndex = low + random.nextInt(high - low + 1);
// 将随机选择的枢轴元素交换到最后
int temp = arr[randomIndex];
arr[randomIndex] = arr[high];
arr[high] = temp;
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
随机选择枢轴可以让快速排序在大多数情况下都能保持较好的性能，平均时间复杂度接近 $O(n log n)$。
三数取中法
三数取中法是指从数组的开头、中间和结尾三个位置选取元素，然后取这三个元素的中位数作为枢轴。
以下是三数取中法的 Java 代码示例：
// Java 技术栈
public class QuickSortMedianOfThree {
// 快速排序主方法
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 int partition(int[] arr, int low, int high) {
// 三数取中
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid]) {
swap(arr, low, mid);
}
if (arr[low] > arr[high]) {
swap(arr, low, high);
}
if (arr[mid] > arr[high]) {
swap(arr, mid, high);
}
// 将中间元素交换到最后作为枢轴
swap(arr, mid, high);
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
// 交换元素的方法
public 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 = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
三数取中法可以在一定程度上保证划分的平衡性，减少最坏情况的发生。
四、应用场景
快速排序在很多场景下都有广泛应用。比如在数据库中对数据进行排序，在搜索引擎中对搜索结果进行排序等。当数据量较大时，快速排序的平均性能优势就会体现出来。
五、技术优缺点
优点
- 速度快：平均时间复杂度为 $O(n log n)$，在处理大规模数据时效率较高。
- 原地排序：不需要额外的存储空间，只需要常数级的额外空间。
缺点
- 最坏情况性能差：如果枢轴元素选择不当，最坏情况下时间复杂度会达到 $O(n^2)$。
- 不稳定排序：快速排序是一种不稳定的排序算法，即相等元素的相对顺序可能会改变。
六、注意事项
- 枢轴元素选择：选择合适的枢轴元素是避免最坏情况的关键，可以根据实际情况选择随机选择枢轴或三数取中法。
- 数据规模：对于小规模数据，快速排序的优势可能不明显，此时可以考虑使用其他简单的排序算法，如插入排序。
七、文章总结
快速排序是一种非常实用的排序算法，但它的性能很大程度上取决于枢轴元素的选择。通过随机选择枢轴或使用三数取中法，可以有效地避免最坏情况的发生，让快速排序在大多数情况下都能保持较好的性能。在实际应用中，我们要根据数据的特点和规模选择合适的枢轴元素选择方法，以达到最佳的排序效果。
评论