了解快速排序算法（附Java示例）

QuickSort 算法详解：高效的排序利器

快速排序 (QuickSort) 是一种基于分治策略的高效排序算法。分治法将问题分解成更小的子问题，分别解决这些子问题，然后组合子问题的解得到最终解。在快速排序中，数组通过选择一个分区元素来划分，该元素决定数组的分割点。在划分之前，分区元素的位置会重新排列，使其位于大于它的元素之前，小于它的元素之后。左右子数组将以这种方式递归划分，直到每个子数组只包含一个元素，此时数组已排序。

快速排序工作原理

让我们以升序排序以下数组为例：

步骤 1：选择枢轴元素

我们选择最后一个元素作为枢轴：

步骤 2：重新排列枢轴元素

我们将枢轴元素放置在其大于它的元素之前，小于它的元素之后。为此，我们将遍历数组，并将枢轴与它之前的每个元素进行比较。如果找到一个大于枢轴的元素，我们为它创建一个第二个指针：

如果找到一个小于枢轴的元素，我们将它与第二个指针交换：

重复此过程，将下一个大于枢轴的元素设置为第二个指针，如果找到小于枢轴的元素则进行交换：

继续此过程直到到达数组的末尾：

完成元素比较后，小于枢轴的元素已移动到右侧，然后我们将枢轴与第二个指针交换：

步骤 3：划分数组

根据分区索引划分数组。如果我们将数组表示为 arr[start..end]，则通过分区划分数组，可以得到左子数组 arr[start..partitionIndex-1] 和右子数组 arr[partitionIndex 1..end]。

以这种方式继续划分子数组，直到每个子数组只包含一个元素：

此时，数组已排序。

快速排序代码实现

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);
        }
    }
}

代码解读

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中文网其他相关文章！