简介

快速排序（Quick Sort）是一种常用的排序算法，又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

它的基本思想是通过不断地划分数组，将小于某个基准值的元素放在基准值的左侧，大于基准值的元素放在基准值的右侧，然后对左右两侧的子数组分别进行快速排序。这个过程不断地递归执行，直到整个数组有序。

步骤

快速排序算法的基本步骤如下：

  1. 选择基准值（通常选择数组的第一个或最后一个元素）。

  2. 设定两个指针，一个指向数组的起始位置（一般称为 low），一个指向数组的结束位置（一般称为 high）。

  3. 从 high 开始，向前搜索，找到第一个小于等于基准值的元素，并将其与 low 指向的元素交换。

  4. 从 low 开始，向后搜索，找到第一个大于基准值的元素，并将其与 high 指向的元素交换。

  5. 重复步骤 3 和步骤 4，直到 low 和 high 相遇。

  6. 将基准值放到相遇位置，此时基准值左侧的元素都小于等于基准值，右侧的元素都大于基准值。

  7. 对基准值左侧的子数组和右侧的子数组分别递归执行上述步骤。

实战案例

下面是使用 Java 实现的快速排序算法的示例代码：

public class QuickSort {
    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }
​
    private static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }
​
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
​
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                swap(array, i, j);
            }
        }
​
        swap(array, i + 1, high);
        return i + 1;
    }
​
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
​
    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 3, 7};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
​

这将输出 [1, 2, 3, 5, 7, 9]，表示数组已经按照从小到大的顺序排序好了。