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

简介

快速排序（Quicksort）是由东尼·霍尔所发展的一种排序算法，在平均状况下，排序 ( n ) 个项目要 ( O(n \log n) ) 次比较。在最坏状况下则需要 ( O(n^2) ) 次比较，但这种状况并不常见。快速排序通常明显比其他 ( O(n \log n) ) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。本文将详细介绍Java中快速排序算法的基础概念、使用方法、常见实践以及最佳实践。

目录

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

基础概念

快速排序是一种分治算法。它的基本步骤如下： 1. 选择基准值（pivot）：从数组中选择一个元素作为基准值。这个元素将用于划分数组。 2. 划分操作（partition）：通过比较和交换元素，将数组分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。 3. 递归排序：对左右两部分分别递归地进行上述步骤，直到整个数组有序。

使用方法

代码示例

public class QuickSort {

    // 划分函数
    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]（pivot）
        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) {
            // pi 是划分点，arr[pi] 现在在正确的位置
            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};
        quickSort(arr, 0, arr.length - 1);

        // 输出排序后的数组
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码解释

1. partition 方法：
   • 选择数组的最后一个元素作为基准值 pivot。
   • 使用指针 i 来跟踪小于等于基准值的元素的边界。
   • 遍历数组，将小于等于基准值的元素交换到左边。
   • 最后将基准值与 i + 1 位置的元素交换，使得左边元素都小于等于基准值，右边元素都大于等于基准值。
2. quickSort 方法：
   • 递归地对左右两部分进行排序，直到整个数组有序。

常见实践

优化基准值选择

1. 随机选择基准值：为了避免最坏情况的发生，可以随机选择基准值。

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

    // 将随机选择的基准值与最后一个元素交换
    int temp = arr[randomIndex];
    arr[randomIndex] = 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;
}

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

小规模数组优化

当数组规模较小时，快速排序的递归调用开销可能较大，此时可以切换到插入排序等简单排序算法。

private static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        if (high - low + 1 <= 16) {
            // 切换到插入排序
            insertionSort(arr, low, high);
            return;
        }

        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.Stack;

public class IterativeQuickSort {

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

    public static void iterativeQuickSort(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(arr.length - 1);

        while (!stack.isEmpty()) {
            int high = stack.pop();
            int low = stack.pop();

            int pi = partition(arr, low, high);

            if (pi - 1 > low) {
                stack.push(low);
                stack.push(pi - 1);
            }
            if (pi + 1 < high) {
                stack.push(pi + 1);
                stack.push(high);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        iterativeQuickSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

并行化处理

在多核处理器环境下，可以使用并行化的快速排序算法来提高性能。Java 8 提供的 ForkJoinPool 可以帮助实现这一点。

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class ParallelQuickSort {

    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 class QuickSortTask extends RecursiveAction {
        private static final int THRESHOLD = 100;
        private final int[] arr;
        private final int low;
        private final int high;

        public QuickSortTask(int[] arr, int low, int high) {
            this.arr = arr;
            this.low = low;
            this.high = high;
        }

        @Override
        protected void compute() {
            if (low < high) {
                if (high - low + 1 <= THRESHOLD) {
                    insertionSort(arr, low, high);
                } else {
                    int pi = partition(arr, low, high);

                    QuickSortTask leftTask = new QuickSortTask(arr, low, pi - 1);
                    QuickSortTask rightTask = new QuickSortTask(arr, pi + 1, high);

                    leftTask.fork();
                    rightTask.compute();
                    leftTask.join();
                }
            }
        }
    }

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

    public static void parallelQuickSort(int[] arr) {
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        forkJoinPool.invoke(new QuickSortTask(arr, 0, arr.length - 1));
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        parallelQuickSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

小结

快速排序是一种高效的排序算法，通过合理选择基准值、优化小规模数组处理以及采用并行化等方法，可以进一步提升其性能。在实际应用中，需要根据数据规模、数据特征以及运行环境等因素来选择合适的优化策略，以达到最佳的排序效果。

参考资料

1. 《算法导论》（Introduction to Algorithms）
2. 维基百科 - 快速排序