快速排序

基本思想

快速排序的基本思想就是类似于分书。我记得我学快速排序听到的故事就是分书的故事。
有一堆书他们有相应的序号，现在图书管理员希望你帮他把这些书按序号从小到大分好给他。我们采取的方案是把第一本书作为基准，把序号比他大的丢到右边，序号比他小的丢到左边。从而我们一直分直到所有的书都按顺序排好为止。

只要左右分的方法我们就称为快速排序。

代码实现

public class Main {
    public void quickSort(int[] arr, int l, int r) {
        if(l < r) {
            int pivot = partition(arr, l, r);
            quickSort(arr, l, pivot);
            quickSort(arr, pivot+1, r);
        }
    }

    public int partition(int[] arr, int l, int r) {
        int pivot = arr[l];
        while(l < r) {
            while(l < r && arr[r] >= pivot) r--;
            arr[l] = arr[r];
            while(l < r && arr[l] <= pivot) l++;
            arr[r] = arr[l];
        }
        arr[l] = pivot;
        return l;
    }
}