快速排序

快速排序使用分治法策略，分 就是把一个序列分为较小数值和较大数值的2个子序列，治 就是通过递归地排序两个子序列

快速排序的步骤是：

1. 挑选基准值：从数列中挑出一个元素，称为基准
2. 分割：重新排列数列，所有比基准小的元素摆放在基准前面，所以比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成
3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序

递归终止条件是数列的大小是零或一，此时该数列显然已经有序了。

public class Application {
    public static void qSort(int[] arr, int head, int tail){
        if(head >= tail || arr == null || arr.length <= 1){
            return;
        }
        int i = head;
        int j = tail;
        int pivot = arr[(head + tail) / 2];

        while (i <= j){
            while (arr[i] < pivot){
                ++i;
            }
            while (arr[j] > pivot){
                --j;
            }
            if(i < j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;
            }else if(i == j){

                ++i;
            }
        }

        qSort(arr,head,j);
        qSort(arr,i,tail);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 4, 8, 2, 55, 3, 4, 8, 6, 4, 0, 11, 34, 90, 23, 54, 77, 9, 2, 9, 4, 10};
        qSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}