跳转至

深入理解 Java 中的快速排序算法

简介

快速排序（QuickSort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在 1960 年发明。它采用了分治（Divide and Conquer）的思想，在平均情况下具有 O(n log n) 的时间复杂度，使其成为实际应用中最常用的排序算法之一。本文将深入探讨快速排序算法在 Java 中的实现，包括基础概念、使用方法、常见实践以及最佳实践。

目录

  1. 基础概念
  2. 使用方法
  3. 常见实践
  4. 最佳实践
  5. 代码示例
  6. 小结
  7. 参考资料

基础概念

快速排序的核心思想是通过选择一个基准值（pivot），将数组分为两部分：一部分元素小于基准值，另一部分元素大于基准值。然后递归地对这两部分进行同样的操作，直到整个数组有序。

具体步骤

  1. 选择基准值：从数组中选择一个元素作为基准值。常见的选择方法有选择第一个元素、最后一个元素或随机选择一个元素。
  2. 分区操作：通过比较和交换元素，将数组分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。
  3. 递归排序：对左右两部分分别递归地应用上述步骤，直到子数组的大小为 1 或 0，此时数组已经有序。

使用方法

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

    // 分区方法
    private 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++;

                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 交换 arr[i+1] 和 arr[high]（基准值）
        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 + " ");
        }
    }
}

代码说明

  1. quickSort 方法：这是主排序方法，接收一个整数数组、起始索引和结束索引。如果起始索引小于结束索引，则调用 partition 方法进行分区，并递归地对左右两部分进行排序。
  2. partition 方法：选择数组的最后一个元素作为基准值，通过遍历数组，将小于等于基准值的元素交换到左边，大于基准值的元素交换到右边。最后返回基准值的索引。
  3. main 方法：用于测试快速排序算法，创建一个示例数组并调用 quickSort 方法进行排序，然后输出排序后的数组。

常见实践

随机选择基准值

为了避免在某些特殊情况下（如数组已经有序）快速排序的性能下降，可以随机选择基准值。

private static int partition(int[] arr, int low, int high) {
    // 随机选择基准值
    int pivotIndex = low + (int) (Math.random() * (high - low + 1));
    int pivot = arr[pivotIndex];

    // 将基准值与最后一个元素交换
    int temp = arr[pivotIndex];
    arr[pivotIndex] = arr[high];
    arr[high] = temp;

    // 后续分区操作与之前相同
    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;
}

三数取中选择基准值

另一种选择基准值的方法是三数取中，即选择数组的第一个、中间和最后一个元素中的中间值作为基准值。

private static int partition(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;

    // 比较并交换，使 arr[low] <= arr[mid] <= arr[high]
    if (arr[low] > arr[mid]) {
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
    }
    if (arr[mid] > arr[high]) {
        int temp = arr[mid];
        arr[mid] = arr[high];
        arr[high] = temp;
    }
    if (arr[low] > arr[mid]) {
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
    }

    // 将基准值（中间值）与最后一个元素交换
    int pivot = arr[mid];
    int temp = arr[mid];
    arr[mid] = arr[high];
    arr[high] = temp;

    // 后续分区操作与之前相同
    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 quickSort(int[] arr, int low, int high) {
    if (low < high) {
        if (high - low + 1 <= 16) {
            // 小数组时使用插入排序
            insertionSort(arr, low, high);
        } else {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
}

private static void insertionSort(int[] arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

并行化快速排序

在多核处理器环境下，可以利用多线程并行化快速排序。通过递归地将任务分配给不同的线程来提高排序效率。

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class ParallelQuickSort {

    private static final int THRESHOLD = 1000; // 任务划分阈值

    public static void parallelQuickSort(int[] arr) {
        ExecutorService executorService = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
        try {
            parallelQuickSort(arr, 0, arr.length - 1, executorService);
        } finally {
            executorService.shutdown();
            try {
                if (!executorService.awaitTermination(60, TimeUnit.SECONDS)) {
                    executorService.shutdownNow();
                }
            } catch (InterruptedException e) {
                executorService.shutdownNow();
                Thread.currentThread().interrupt();
            }
        }
    }

    private static void parallelQuickSort(int[] arr, int low, int high, ExecutorService executorService) {
        if (low < high) {
            if (high - low + 1 <= THRESHOLD) {
                quickSort(arr, low, high);
            } else {
                int pi = partition(arr, low, high);

                executorService.submit(() -> parallelQuickSort(arr, low, pi - 1, executorService));
                executorService.submit(() -> parallelQuickSort(arr, pi + 1, high, executorService));
            }
        }
    }

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

    private 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 void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        parallelQuickSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

小结

快速排序是一种高效的排序算法，在 Java 中实现快速排序需要理解其核心思想和基本步骤。通过选择合适的基准值、优化小数组排序以及并行化处理，可以进一步提高快速排序的性能。在实际应用中，根据具体的需求和数据特点选择合适的优化策略，能够充分发挥快速排序算法的优势。

参考资料