快速排序：高效的分治排序算法
快速排序是一种基于分治策略的高效排序算法。它将问题分解成更小的子问题，分别解决后再合并结果，最终得到排序后的数组。核心在于选择一个“枢轴”（pivot）元素，将数组划分成两部分：小于枢轴的元素和大于枢轴的元素。然后递归地对这两部分进行排序。
快速排序工作原理详解
假设我们需要对一个数组进行升序排序：
立即学习“Java免费学习笔记（深入）”；
步骤1：选择枢轴
我们选择数组的最后一个元素作为枢轴：
步骤2：数组划分
遍历数组，将小于枢轴的元素移动到枢轴左侧，大于枢轴的元素移动到枢轴右侧。为此，我们使用两个指针：一个指向当前遍历元素，另一个指向小于枢轴元素区域的末尾。
最后，将枢轴与小于枢轴元素区域的末尾元素交换：
步骤3：递归排序
根据枢轴的位置，将数组划分成两个子数组，并递归地对这两个子数组应用快速排序算法，直到子数组只有一个元素（此时已排序）。
快速排序代码实现
public class QuicksortTest {
public static void main(String[] args) {
int[] arr = {8, 6, 2, 3, 9, 4};
System.out.println("Unsorted array: " + java.util.Arrays.toString(arr));
quicksort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
}
public static void quicksort(int[] arr, int start, int end) {
if (start < end) {
int partitionIndex = partition(arr, start, end);
quicksort(arr, start, partitionIndex - 1);
quicksort(arr, partitionIndex + 1, end);
}
}
public static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int secondPointer = start - 1;
for (int i = start; i < end; i++) {
if (arr[i] < pivot) {
secondPointer++;
swap(arr, i, secondPointer);
}
}
swap(arr, end, secondPointer + 1);
return secondPointer + 1;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
代码解读：
-
quicksort方法实现递归排序，当子数组只有一个元素时停止递归。 -
partition方法实现数组划分，返回枢轴的最终位置。 -
swap方法交换数组中两个元素的位置。
时间和空间复杂度
- 最佳情况时间复杂度：O(n log n) 每次划分都将数组分成大小近乎相等的两部分。
- 平均情况时间复杂度：O(n log n)
- 最坏情况时间复杂度：O(n²) 每次划分都将数组分成一个元素和其余元素两部分（例如，已排序数组）。
- 空间复杂度：O(log n) 递归调用栈的空间复杂度。
总结
快速排序是一种平均时间复杂度为 O(n log n) 的高效排序算法，但在最坏情况下时间复杂度会退化为 O(n²)。其性能很大程度上依赖于枢轴的选择策略。 通过合适的枢轴选择和优化，可以有效避免最坏情况的发生，使其成为实际应用中常用的排序算法。
