Java 实现快速排序算法：一条快速通道，分而治之

大家好，今天我们来聊聊快速排序（QuickSort）算法，这个经典的排序算法被广泛应用于各种需要高效排序的场景。作为一种分治法（Divide and Conquer）算法，快速排序的效率在平均情况下非常高，是大多数排序算法中的“黄金选手”。那么，让我们一起来了解如何在 Java 中实现快速排序吧！

一、什么是快速排序？

快速排序是一种基于分治法的排序算法，它的基本思想是通过选择一个“基准”元素，将待排序的数组分成两个子数组，使得一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素。然后对这两个子数组递归执行快速排序，最终完成排序。

快速排序的步骤：

1. 从数组中选择一个元素作为“基准”（pivot）。
2. 将数组中所有比基准小的元素移到基准的左边，比基准大的元素移到基准的右边。
3. 递归地对基准左边和右边的子数组进行排序。
4. 当子数组的大小为 1 或者 0 时，停止递归，因为它们已经是有序的。

二、快速排序的时间复杂度

快速排序的时间复杂度是O(n log n)，但在最坏情况下（比如每次选取的基准元素都是最小或最大的元素），它的时间复杂度会退化到O(n²)。然而，在平均情况下，快速排序的表现非常优秀，因此它通常被认为是高效的排序算法之一。

• 最好和平均时间复杂度：O(n log n)
• 最坏时间复杂度：O(n²)
• 空间复杂度：O(log n)

三、Java 快速排序的实现

在 Java 中实现快速排序，我们需要编写一个递归函数来进行分割和排序。具体步骤如下：

1. 选择基准元素：常见的选择方式是选取数组的第一个元素、最后一个元素、或随机选择一个元素作为基准。
2. 划分数组：通过一个指针将数组分成两个部分，一部分小于基准，另一部分大于基准。
3. 递归排序子数组：对左边和右边的子数组分别递归执行快速排序。

下面是 Java 实现快速排序的代码：

public class QuickSort {public static void sort(int[] arr, int left, int right) {//递归跳出条件：每个左右子数组的长度为1，大于和等于都要有if (left >= right) {return;}//基准数int base = arr[left];int i = left;int j = right;while (i < j) {//注意先从右向左找，注意没有等号while (arr[j] > base && j > i) {j--;}//再从左往右找，注意要有等号while (arr[i] <= base && i < j) {i++;}//如果因为i = j跳出循环，那么没必要进行交换if (i < j) {//交换两元素位置int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}//交换基准与i=j的位置arr[left] = arr[i];arr[i] = base;//左右子数组递归排序sort(arr,left, i - 1);sort(arr, i + 1, right);}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);}
}

四、代码解析

1. quickSort 方法：这是快速排序的递归入口函数。它接收一个数组和数组的下标 low 和 high，表示待排序数组的范围。如果 low 小于 high，就调用 partition 方法来划分数组并递归排序。

2. partition 方法：该方法用于选择基准元素并将数组划分为两部分：

   • 所有小于基准的元素排在基准的左边。
   • 所有大于基准的元素排在基准的右边。 最后，基准元素会被放到它的正确位置，并返回该位置的索引。

3. swap 方法：用于交换数组中两个元素的位置。

4. printArray 方法：用于打印数组，便于观察排序结果。

五、输出结果

假设我们使用的数组是 {10, 7, 8, 9, 1, 5}，那么运行上述代码后的输出将会是：

原始数组：
10 7 8 9 1 5 
排序后的数组：
1 5 7 8 9 10 

可以看到，数组成功地按照从小到大的顺序进行了排序。

六、优化与扩展

1. 选择基准优化：

   • 在选择基准时，避免总是选取第一个或最后一个元素，可以通过三数取中法来选择基准元素，从而避免在已经部分有序的数组中出现最坏情况（O(n²)）。

   示例：

   int mid = low + (high - low) / 2;
   int pivot = medianOfThree(arr[low], arr[mid], arr[high]);
   

2. 尾递归优化：

   快速排序是递归的，递归深度可能较深。通过尾递归优化，可以将较小的子数组放在栈中，而将较大的子数组先处理，减少栈的深度。

3. 非递归实现：

   快速排序也可以通过栈实现非递归版本，避免递归过深导致栈溢出。

七、小结

快速排序是一个高效的排序算法，通过分治法将问题逐步简化。尽管它在最坏情况下的时间复杂度是 O(n²)，但在平均情况下，其表现非常优异，尤其是在处理大量数据时。如果能优化基准选择，快速排序的效率会进一步提升。希望通过本文的介绍，你对快速排序有了更深入的了解，并且能够在 Java 中轻松实现这一经典算法！