介绍

快速排序是由东尼·霍尔所发展的一种排序算法，该算法采用了“分治思想”，同时快速排序由于排序效率在同为O(n*logn)的几种排序方法中效率较高，因此经常被采用。

时间复杂度：

• 最好情况：O(nlogn)
• 平均情况：O(nlogn)
• 最坏情况：O(n^2)

稳定性：不稳定（不稳定发生在基准元素flag与arr[index+1]交换时）

额外的空间：O(logn)~O(n)

过程

1. 从序列中将某一个元素（通常为最后一个）作为基准
2. 大于基准的元素放在基准的右边，小于基准的元素放在基准的左边，将一个序列分为两个序列，该过程为称为分区
3. 对于每个分区，递归执行步骤1、2，直至序列大小为0或1时跳出递归，此时排序已经完成

文字描述可能不够形象，看图示更能理解：

Java实现

/*
 * QuickSort.java:快速排序
 */
import java.util.Arrays;

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

    //快速排序
    private static void quickSort(int[] arr, int left, int right) {
        //当左边大于或等于右边此时分区大小为0或1时跳出递归
        if (left >= right) {
            return;
        }
        int flagIndex = partition(arr, left, right);//设置基准索引
        //从左往右递归
        quickSort(arr, left, flagIndex - 1);
        quickSort(arr, flagIndex + 1, right);
    }

    //划分数组并返回基准索引
    private static int partition(int[] arr, int left, int right) {
        int flag = arr[right];//将最后一个元素设置为基准
        int index = left - 1;//左边第一个元素的前一个元素索引
        for (int i = left; i < right; i++) {
            //若小于基准则将其排到前面
            if (arr[i] <= flag) {
                swap(arr, ++index, i);
            }
        }
        swap(arr, index + 1, right);//将基准插入到正确位置
        return index + 1;//返回基准索引
    }

    //交换数组元素
    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}