Java 排序算法之快速排序

快速排序（Quick Sort）是一种高效的排序算法，属于分治法（Divide and Conquer）策略，它的时间复杂度为 $O(nlogn)$，在大多数情况下可以达到线性级别的时间复杂度，是非常重要且常用的排序算法之一。

基本思想

快速排序算法的基本思路是：选择一个元素作为数组的 “基准”（pivot），将小于基准的元素放到它的左边，将大于基准的元素放到它的右边，然后再分别对基准的左半边和右半边进行递归操作。

算法步骤

1. 首先需要选择一个基准元素（pivot），一般可以选择数组的第一个元素或最后一个元素作为基准元素。

2. 将数组中小于基准元素的放到基准元素的左侧，大于基准元素的放到基准元素的右侧。

3. 对基准元素左边的子数组和右边的子数组进行递归操作，直到子数组的长度为 1或0时，停止递归操作。

示例说明

示例 1

假设我们有一个整型数组：

int[] arr = { 5, 3, 8, 6, 2, 7, 1, 4 };

按照快速排序算法的步骤，我们首先需要选择一个基准元素。这里我们选择数组的第一个元素 5 作为基准元素。

为了方便演示，我们可以使用以下程序代码实现 partition：

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = { 5, 3, 8, 6, 2, 7, 1, 4 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static int partition(int[] arr, int left, int right) {
        int i = left + 1, j = right;
        while (true) {
            while (i <= j && arr[i] < arr[left]) {
                i++;
            }
            while (i <= j && arr[j] > arr[left]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
        int temp = arr[left];
        arr[left] = arr[j];
        arr[j] = temp;
        return j;
    }

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

}

在 partition 方法中，我们从数组的第 2 个元素开始向右查找，直到找到大于或等于基准元素的元素，同时从数组的最后一个元素开始向左查找，直到找到小于或等于基准元素的元素。如果找到了这样的情况，我们将两个元素交换。如果左右指针相遇，我们就跳出循环。最后我们将基准元素与左指针指向的元素交换。

在调用 quickSort 方法时，将数组和分别指向数组的起始位置和末尾位置的下标作为参数传递进去。在每次递归时，就根据基准元素的位置将数组分成两个子数组，然后分别对它们进行递归操作。

最终的输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8]

示例 2

假设我们有一个字符串数组：

String[] arr = {"c", "a", "e", "b", "d"};

按照快速排序算法的步骤，我们首先需要选择一个基准元素。这里我们选择数组的第一个元素 c 作为基准元素。

为了方便演示，我们可以使用以下程序代码实现 partition：

public class QuickSort {

    public static void main(String[] args) {
        String[] arr = { "c", "a", "e", "b", "d" };
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static int partition(String[] arr, int left, int right) {
        int i = left + 1, j = right;
        while (true) {
            while (i <= j && arr[i].compareTo(arr[left]) < 0) {
                i++;
            }
            while (i <= j && arr[j].compareTo(arr[left]) > 0) {
                j--;
            }
            if (i >= j) {
                break;
            }
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
        String temp = arr[left];
        arr[left] = arr[j];
        arr[j] = temp;
        return j;
    }

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

}

在 partition 方法中，我们从数组的第 2 个元素开始向右查找，直到找到大于或等于基准元素的元素，同时从数组的最后一个元素开始向左查找，直到找到小于或等于基准元素的元素。如果找到了这样的情况，我们将两个元素交换。如果左右指针相遇，我们就跳出循环。最后我们将基准元素与左指针指向的元素交换。

在调用 quickSort 方法时，将数组和分别指向数组的起始位置和末尾位置的下标作为参数传递进去。在每次递归时，就根据基准元素的位置将数组分成两个子数组，然后分别对它们进行递归操作。

最终的输出结果为：

[a, b, c, d, e]

总结

快速排序算法是一种高效的排序算法，常用于实际生产环境中的排序任务。它的优势在于其时间复杂度和空间复杂度较低，在大多数情况下可以达到线性级别的时间复杂度