快速排序（时间复杂度：O(N*logN)）

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。
它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
最坏运行情况是 O(n²)

动图演示：

快速排序gif

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

代码演示（java)

/**
 * 快速排序
 * 分成两组,和中间值进行比较,小的放左边,大的放右边;
 *
 *
 * @param arr 需要排序的数组
 * @param l   左边的下标,从最左边开始
 * @param r   右边的下标,从最右边开始
 */
public static void sort(int[] arr, int l, int r) {
    // 左边下标
    int left = l;
    // 右边下标
    int right = r;
    // 中间值, TODO 注意：不能用数组的长度,否则得到的不是中间值
    int middle = arr[(l + r) / 2];
    // 临时变量,用于辅助交换
    int temp;

    // 和中间值进行小的放左边，大的放右边
    while (left < right) {

        // 从左边开始遍历,小于中间值则放左边
        while (arr[left] < middle) {
            left += 1;
        }
        // 从右边开始遍历，大于中间值则放右边
        while (arr[right] > middle) {
            right -= 1;
        }
        // 左边下标 >= 右边下标则比较结束
        if (left >= right) {
            break;
        }
        // 交换,整个方法只有这里进行了排序.
        temp = arr[right];
        arr[right] = arr[left];
        arr[left] = temp;

        // 如果左边和中间值相等,则右边下标左移
        if (arr[left] == middle) {
            right -= 1;
        }
        // 如果右边和中间值相等，则左边下标右移
        if (arr[right] == middle) {
            left += 1;
        }
    }
    // 如果相等则继续移动,避免栈溢出
    if (right == left) {
        left += 1;
        right -= 1;
    }

    // 向左边递归
    if (l < right) {
        sort(arr, l, right);
    }
    // 向右边递归
    if (r > left) {
        sort(arr, left, r);
    }

}