数据结构第20节 快速排序以及优化

快速排序是一种非常高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年代发明。它使用分治法（Divide and Conquer）策略来把一个序列分为较小的部分，然后递归地排序这些部分。

快速排序的基本步骤：

1. 选择基准值（Pivot Selection）：从序列中选择一个元素作为基准值。通常选择序列的第一个、最后一个或中间的元素，也可以随机选择。
2. 分区操作（Partitioning）：重新排列序列，使得所有小于基准值的元素都位于基准值的左边，所有大于基准值的元素都位于基准值的右边。完成这个操作后，基准值就位于最终排序后的位置。
3. 递归排序子序列：递归地对基准值左边和右边的子序列应用快速排序算法。

分区操作细节：

• 设置两个指针 left 和 right，left 指针从序列的起始位置开始，right 指针从序列的结束位置开始。
• 移动 right 指针，直到找到一个小于或等于基准值的元素。
• 移动 left 指针，直到找到一个大于或等于基准值的元素。
• 如果 left 指针在 right 指针的左边，交换两个指针所指向的元素。
• 重复上述步骤，直到 left 和 right 指针相遇或交叉。
• 当指针交叉时，将基准值与 right 指针所指向的元素交换，完成分区操作。

Java代码实现：

下面是一个简单的快速排序算法的Java实现：

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // pi is partitioning index, arr[pi] is now at right place
            int pi = partition(arr, low, high);

            // Recursively sort elements before and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // pivot
        int i = (low - 1); // Index of smaller element

        for (int j = low; j < high; j++) {
            // If current element is smaller than the pivot
            if (arr[j] < pivot) {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    // Function to print an array
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

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

        quickSort(arr, 0, n - 1);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

时间复杂度：

• 最佳和平均情况：O(n log n)
• 最差情况：O(n^2)，当输入数组已经是排序好的或逆序的，基准值每次都是最小或最大值。

空间复杂度：

• O(log n)，由于递归调用栈的空间。

快速排序在实际应用中非常广泛，尤其是在大规模数据集上，因为它能够提供非常好的性能。然而，在某些情况下，例如数据已经接近排序的情况下，快速排序的性能可能会退化，这时可以考虑使用其他排序算法，如堆排序或归并排序。

要优化快速排序算法，我们可以采取几种不同的策略来提高其效率和稳定性。以下是一些常见的改进方法：

1. 三数取中法（Median-of-three）选择基准值：
   在选择基准值时，使用数组的第一个元素、中间元素和最后一个元素中的中位数作为基准值，这有助于避免最坏情况的发生，特别是在数组已经部分排序的情况下。

2. 插入排序小数组：
   对于小规模的子数组，使用插入排序替换快速排序。插入排序在小数组上的性能通常优于快速排序，因为它的常数因子较小。

3. 尾递归优化：
   可以优化递归调用，减少栈空间的使用。具体来说，你可以先递归处理较大的子数组，然后迭代处理较小的子数组，或者使用循环结构替代递归。

4. 非递归版本：
   使用显式栈来模拟递归调用，这样可以避免系统调用栈的开销。

下面是使用三数取中法和插入排序小数组的优化版快速排序示例代码：

public class OptimizedQuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        while (low < high) {
            // Partition and get the partition index.
            int pi = partition(arr, low, high);

            // Recursively sort the left part, but only if it's larger than the right.
            if (pi - low < high - pi) {
                quickSort(arr, low, pi - 1);
                low = pi + 1;
            } else {
                quickSort(arr, pi + 1, high);
                high = pi - 1;
            }
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // Median-of-three pivot selection
        int mid = (low + high) / 2;
        if (arr[mid] > arr[high]) {
            swap(arr, mid, high);
        }
        if (arr[low] > arr[high]) {
            swap(arr, low, high);
        }
        if (arr[mid] > arr[low]) {
            swap(arr, mid, low);
        }
        
        int pivot = arr[low];
        int i = low + 1;
        int j = high;

        while (true) {
            while (i <= j && arr[i] <= pivot) {
                i++;
            }
            while (i <= j && arr[j] >= pivot) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
            } else {
                break;
            }
        }

        swap(arr, low, j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public 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--;
            }
            arr[j + 1] = key;
        }
    }

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

        // Optimize: Use insertion sort for small subarrays
        for (int i = 0; i < n; i += 16) {
            insertionSort(arr, i, Math.min((i + 15), (n - 1)));
        }

        quickSort(arr, 0, n - 1);

        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

在这个优化版本中，我们使用了三数取中法来选择更合理的基准值，并且对于小于16个元素的小数组使用插入排序进行排序。此外，我们还通过循环结构代替递归来减少栈的使用。这些修改可以帮助提高快速排序在各种情况下的性能和稳定性。

尾递归优化

尾递归优化是指在递归函数中，如果递归调用是函数执行的最后一个操作，那么可以通过一些技巧将其转换为迭代，从而避免栈溢出的风险和减少递归调用的开销。对于快速排序而言，可以优先递归处理较小的子数组，然后返回处理较大的子数组，这样可以保证递归深度不会过大。

下面是一个利用尾递归优化的快速排序Java实现示例：

public class TailRecursiveQuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        while (low < high) {
            // Partitioning index
            int pi = partition(arr, low, high);

            // Recursively sort elements before partition and after partition
            if (pi - low < high - pi) {
                // Sort the smaller part first
                quickSort(arr, low, pi - 1);
                // Update the range for the larger part
                low = pi + 1;
            } else {
                // Sort the larger part first
                quickSort(arr, pi + 1, high);
                // Update the range for the smaller part
                high = pi - 1;
            }
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1); // index of smaller element
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            if (arr[j] <= pivot) {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        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};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

在这个版本中，quickSort 函数使用了一个循环来处理子数组的排序。在每次循环中，它首先对当前的子数组进行分区操作，然后根据左右两部分的大小决定先递归处理哪一部分。这样做可以确保每次递归调用之后，剩余需要处理的子数组的大小总是比前一次小，从而减少了递归的深度。

然而，值得注意的是，尽管这种优化减少了递归调用的次数，但在最坏情况下，如果每次分区都偏向一侧，递归深度仍然可能较大。因此，结合其他优化策略，如三数取中法选择基准值，可以进一步提高算法的稳定性和性能。

为了进一步提高快速排序的稳定性和性能，可以结合多种优化策略。以下是几种常见的改进方法：

1. 三数取中法选择基准值：选取第一个、中间的和最后一个元素中的中值作为基准值，以减少最坏情况的发生。

2. 插入排序小数组：对于小规模的子数组，使用插入排序。插入排序在小数组上的效率高于快速排序。

3. 随机化基准值选择：随机选择数组中的一个元素作为基准值，可以避免最坏情况的发生，尤其是当数组已部分排序时。

4. 双路快速排序（Dual-Pivot QuickSort）：同时使用两个基准值，可以减少比较和交换的次数，从而提高性能。

5. 尾递归优化：减少递归调用的深度，使用循环结构替代递归。

6. 并行化：利用多核处理器的优势，使用并行计算技术对子数组进行排序。

下面是一个结合了三数取中法、插入排序小数组和尾递归优化的快速排序Java实现：

public class OptimizedQuickSort {

    private static final int INSERTION_SORT_THRESHOLD = 16; // 阈值用于插入排序

    public static void quickSort(int[] arr, int low, int high) {
        while (low < high) {
            // 使用三数取中法选择基准值
            int pivotIndex = medianOfThree(arr, low, high);
            int pivot = arr[pivotIndex];

            // 将基准值放到最后
            swap(arr, pivotIndex, high);

            // Partitioning index
            int pi = partition(arr, low, high);

            // Recursively sort elements before partition and after partition
            if (pi - low < high - pi) {
                // Sort the smaller part first
                quickSort(arr, low, pi - 1);
                // Update the range for the larger part
                low = pi + 1;
            } else {
                // Sort the larger part first
                quickSort(arr, pi + 1, high);
                // Update the range for the smaller part
                high = pi - 1;
            }
        }
    }

    private static int medianOfThree(int[] arr, int low, int high) {
        int mid = (low + high) >>> 1; // 使用无符号右移获得中间索引
        if (arr[mid] > arr[high]) {
            swap(arr, mid, high);
        }
        if (arr[low] > arr[high]) {
            swap(arr, low, high);
        }
        if (arr[mid] > arr[low]) {
            swap(arr, mid, low);
        }
        return low; // 返回中位数的索引
    }

    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++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public 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--;
            }
            arr[j + 1] = key;
        }
    }

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

        // 使用插入排序处理小数组
        for (int i = 0; i < n; i += INSERTION_SORT_THRESHOLD) {
            insertionSort(arr, i, Math.min(i + INSERTION_SORT_THRESHOLD - 1, n - 1));
        }

        // 使用快速排序处理大数组
        quickSort(arr, 0, n - 1);

        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

这个版本的快速排序算法结合了多种优化策略，提高了排序的性能和稳定性。在实际应用中，根据数据的特点和环境的限制，还可以尝试其他的优化策略以达到最佳效果。例如，对于大规模数据集，可以考虑使用并行快速排序来充分利用多核处理器的能力。

在Java中，利用并行流（parallel streams）或java.util.concurrent包中的工具可以实现并行快速排序。这里，我将展示如何使用Fork/Join框架来实现并行快速排序。

Fork/Join框架是Java 7引入的一种并行编程模型，它允许任务被分割成更小的任务，然后并行执行。在快速排序中，我们可以将大的数组分割成小的子数组，并在不同的线程上并行地对它们进行排序。

下面是一个使用Fork/Join框架的并行快速排序实现：

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

public class ParallelQuickSort {

    public static void main(String[] args) {
        int[] arr = new int[1_000_000];
        // 初始化数组...
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * 1000);
        }

        long startTime = System.currentTimeMillis();

        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new SortTask(arr, 0, arr.length - 1));

        long endTime = System.currentTimeMillis();
        System.out.println("Sorting took " + (endTime - startTime) + " ms");

        // 检查排序是否正确
        boolean isSorted = true;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                isSorted = false;
                break;
            }
        }
        System.out.println("Is sorted: " + isSorted);
    }

    static class SortTask extends RecursiveAction {
        private final int[] arr;
        private final int low;
        private final int high;

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

        @Override
        protected void compute() {
            if (low < high) {
                int pi = partition(arr, low, high);
                invokeAll(new SortTask(arr, low, pi - 1), new SortTask(arr, pi + 1, high));
            }
        }

        private int partition(int[] arr, int low, int high) {
            int pivot = arr[high];
            int i = (low - 1); // index of smaller element
            for (int j = low; j < high; j++) {
                // If current element is smaller than or equal to pivot
                if (arr[j] <= pivot) {
                    i++;

                    // swap arr[i] and arr[j]
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }

            // swap arr[i+1] and arr[high] (or pivot)
            int temp = arr[i + 1];
            arr[i + 1] = arr[high];
            arr[high] = temp;

            return i + 1;
        }
    }
}

在上述代码中，SortTask继承自RecursiveAction类，这是Fork/Join框架中的一个抽象类，用于表示一个可并行执行的任务。compute方法定义了任务的执行逻辑。当一个SortTask实例被创建并提交给ForkJoinPool时，它会根据子任务的大小决定是继续分割任务还是直接执行。如果任务足够小，它将直接进行排序；如果任务足够大，它将被分割成更小的子任务，并在多个线程上并行执行。

这种方法特别适用于多核处理器，因为它能有效利用所有可用的CPU核心。但是，对于较小的数据集，由于启动额外线程的开销，传统的单线程排序可能会更快。因此，在实际应用中，你可能还需要调整任务分割的阈值，以找到最适合特定硬件配置的平衡点。

优化后的非递归版本的快速排序算法通常使用显式栈来模拟递归调用的行为，从而避免了递归调用带来的栈溢出风险以及函数调用的开销。下面是一个使用显式栈的非递归快速排序算法的Java实现：

import java.util.ArrayDeque;
import java.util.Deque;

public class NonRecursiveQuickSort {

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

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

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

            if (pivotIndex - 1 > low) {
                stack.push(low);
                stack.push(pivotIndex - 1);
            }

            if (pivotIndex + 1 < high) {
                stack.push(pivotIndex + 1);
                stack.push(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++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr);
        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

在这个实现中，我们使用了一个双向队列ArrayDeque作为栈，用于存储待处理的子数组的边界。quickSort函数初始化栈，然后在一个循环中不断弹出栈顶的高边界和低边界，进行分区操作，并根据分区结果更新栈的内容，直到栈为空为止。

这种非递归的方法可以有效地减少内存栈的使用，避免了在递归深度过深时可能出现的栈溢出问题，同时也能保持快速排序的高效性能。在实际应用中，你可以根据具体需求调整分区策略、基准值的选择方法等，以进一步优化排序过程。