JAVA十大排序算法之快速排序详解

算法介绍

快速排序是一种基于分治思想的排序算法，是十大排序算法中非常常用的一种。它的核心思想是取一个基准值，将数组中小于基准值的放在一边，大于它的放在另一边，递归地对两个子集进行排序。通过多次分区排序，最终将整个数组排序。

算法步骤

1. 选择基准值，通常取区间的第一个元素（也可以取随机元素）
2. 分区操作：将区间根据基准值划分为两个子区间，小于等于基准值的放在左边，大于基准值的放在右边
3. 对左右两个子区间分别进行递归操作
4. 递归结束条件：区间大小为1或0

代码实现

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
}

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] > pivot) {
            j--;
        }
        if (i < j) {
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = pivot;
    return i;
}

算法分析

快速排序的平均时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n^2)。空间复杂度为 O(logn)。在实际应用中，快速排序是十大排序算法中平均性能最好的，常用于排序大量数据。

示例说明

以下是对数组 {3, 5, 1, 6, 2, 9, 8, 7, 4} 进行快速排序的过程。

1. 选择基准值 pivot=3，i=0，j=8。
2. 从右往左扫描，找到第一个小于 pivot 的数 arr[j]，交换 arr[i] 和 arr[j]，此时数组为 {2, 5, 1, 6, 3, 9, 8, 7, 4}，i=1，j=4。
3. 从左往右扫描，找到第一个大于 pivot 的数 arr[i]，交换 arr[i] 和 arr[j]，此时数组为 {2, 1, 3, 6, 5, 9, 8, 7, 4}，i=2，j=4。
4. 从右往左扫描，找到第一个小于 pivot 的数 arr[j]，交换 arr[i] 和 arr[j]，此时数组为 {2, 1, 3, 4, 5, 9, 8, 7, 6}，i=3，j=3。
5. 递归左右两个子区间，left=0，right=2 的子区间是 {2, 1, 3}，left=4，right=8 的子区间是 {5, 9, 8, 7, 6}。
6. 对左子区间进行快速排序，选择基准值 pivot=2，i=0，j=2，数组排序为 {1, 2, 3}。
7. 对右子区间进行快速排序，选择基准值 pivot=5，i=0，j=4，数组排序为 {4, 5, 6, 7, 8, 9}。
8. 最终得到有序数组 {1, 2, 3, 4, 5, 6, 7, 8, 9}。

通过以上示例可以清晰地展示快速排序的分区过程，以及如何递归地对子区间进行排序。