QuickSort 算法详解:高效的排序利器
快速排序 (QuickSort) 是一种基于分治策略的高效排序算法。分治法将问题分解成更小的子问题,分别解决这些子问题,然后组合子问题的解得到最终解。在快速排序中,数组通过选择一个分区元素来划分,该元素决定数组的分割点。在划分之前,分区元素的位置会重新排列,使其位于大于它的元素之前,小于它的元素之后。左右子数组将以这种方式递归划分,直到每个子数组只包含一个元素,此时数组已排序。
快速排序工作原理
让我们以升序排序以下数组为例:
步骤 1:选择枢轴元素
我们选择最后一个元素作为枢轴:
步骤 2:重新排列枢轴元素
我们将枢轴元素放置在其大于它的元素之前,小于它的元素之后。为此,我们将遍历数组,并将枢轴与它之前的每个元素进行比较。如果找到一个大于枢轴的元素,我们为它创建一个第二个指针:
如果找到一个小于枢轴的元素,我们将它与第二个指针交换:
重复此过程,将下一个大于枢轴的元素设置为第二个指针,如果找到小于枢轴的元素则进行交换:
继续此过程直到到达数组的末尾:
完成元素比较后,小于枢轴的元素已移动到右侧,然后我们将枢轴与第二个指针交换:
步骤 3:划分数组
根据分区索引划分数组。如果我们将数组表示为 arr[start..end],则通过分区划分数组,可以得到左子数组 arr[start..partitionIndex-1] 和右子数组 arr[partitionIndex 1..end]。
以这种方式继续划分子数组,直到每个子数组只包含一个元素:
此时,数组已排序。
快速排序代码实现
<code class="language-java">import java.util.Arrays; public class QuickSortTest { public static void main(String[] args){ int[] arr = {8, 6, 2, 3, 9, 4}; System.out.println("未排序数组: " + Arrays.toString(arr)); quickSort(arr, 0, arr.length-1); System.out.println("已排序数组: " + Arrays.toString(arr)); } 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++; // 交换元素 int temp = arr[secondPointer]; arr[secondPointer] = arr[i]; arr[i] = temp; } } // 将枢轴与第二个指针交换 int temp = arr[secondPointer+1]; arr[secondPointer+1] = arr[end]; arr[end] = temp; // 返回分区索引 return secondPointer+1; } 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); } } }</code>
代码解读
quickSort
方法:首先调用 partition
方法将数组分成两个子数组,然后递归调用 quickSort
对左右子数组进行排序。这个过程持续进行,直到所有子数组都只包含一个元素,此时数组已排序。
partition
方法:负责将数组分成两个子数组。它首先设置枢轴和下一个较大元素的指针,然后遍历数组,将小于枢轴的元素移动到左侧。之后,它将枢轴与第二个指针交换,并返回分区位置。
运行以上代码,控制台将输出以下内容:
未排序数组: [8, 6, 2, 3, 9, 4] 已排序数组: [2, 3, 4, 6, 8, 9]
时间复杂度
最佳情况 (O(n log n)):当枢轴每次都将数组分成两个几乎相等的部分时,就会出现最佳情况。
平均情况 (O(n log n)):在平均情况下,枢轴将数组分成两个不相等的部分,但递归深度和比较次数仍然与 n log n 成正比。
最坏情况 (O(n²)):当枢轴始终将数组分成非常不相等的部分(例如,一部分只有一个元素,另一部分有 n-1 个元素)时,就会出现最坏情况。例如,当排序一个逆序数组时,并且枢轴选择不佳时,就会发生这种情况。
空间复杂度 (O(log n)):快速排序通常就地实现,不需要额外的数组。
以上是了解快速排序算法(附Java示例)的详细内容。更多信息请关注PHP中文网其他相关文章!