快速排序

快速排序简介

快速排序是一种基于交换的排序方式（另一种基于交换的排序方式是冒泡排序），它的时间复杂度是nlog_2n。它的思路如下
先在元素序列中选择一个元素作为基准（一般选第一个元素），然后进行一次划分操作，划分操作简单说来就是将小于该基准的元素放在基准的左边，将大于该基准的元素放在基准的右边（不需要考虑左边元素是不是有序的，即只要把小于基准的放在左边就行了，不需要考虑到底放在左边的哪个位置。右边元素也是这个道理)。然后递归处理基准左边的序列和基准右边的序列，递归出口是序列中的元素数小于两个时。

划分操作概述

1. 首先设置两个指针，分别指向序列的首尾，令首指针为tmpL, 尾指针为tmpR。
2. 将首元素作为基准保存在变量pivotal中。
3. 当首指针小于尾指针时进行循环

• 先从尾指针出发，往前遍历元素序列，直到找到一个小于pivotal的元素，将这个元素放到首指针的位置（此时首指针指向元素已经存放在另一个位置中了：第一次while循环时存在pivotal变量中，以后就存在上一次循环的尾指针中，所以不用担心首指针指向的元素被覆盖）
• 再从首指针出发，往后遍历元素序列，直到找到一个大于pivotal的元素，将这个元素放到尾指针的位置

4. 退出循环时首指针等于尾指针，且它们就指向了基准元素应该放在的位置，所以将pivotal放进这个位置

Java实现

public class Quick{
    public static void main(String[] args){
        Integer[] integers = {1, 3, 2, 4, 1, 5, 4};
        Quick.sort(integers);
        System.out.println(integers);
    }

    public static void sort(Comparable[] array){
        sort(array, 0, array.length - 1);
    }

    // 划分操作
    @SuppressWarnings("unchecked")
    private static void sort(Comparable[] array, int left, int right){
        Comparable pivotal = array[left];
        int tmpL = left, tmpR = right;
        while (tmpL < tmpR){
            while (tmpR > tmpL && array[tmpR].compareTo(pivotal) >= 0)
                tmpR--;
            array[tmpL] = array[tmpR];
            while (tmpR > tmpL && array[tmpL].compareTo(pivotal) <= 0)
                tmpL++;
            array[tmpR] = array[tmpL];
        }
        array[tmpL] = pivotal;
        if (tmpR - 1 > left)
            sort(array, left, tmpR-1);
        if (tmpR + 1 < right)
            sort(array, tmpR+1, right);
    }
}