排序

public int[] quickSort(int[] arr, int l, int r) {

    if(arr == null || l <= r) return arr;

    int i = l, j = r, x = arr[l];

    while(i < j) {

        while(i < j && arr[j] > x) j--;

        if(i < j) arr[i++] = arr[j];

        while(i < j && arr[i] < x) i++;

        if(i < j) arr[j--] = arr[i];

    }

    arr[i] = x;

    quickSort(arr, l, i-1);

    quickSort(arr, i+1, r);

    return arr;	// 基于原数组修改，其实也可以不用返回

}

// 归并排序

    private int[] mergeSort(int[] arr, int l , int r) {

        up2Down(arr,0,arr.length-1);

        return arr;

    }

    // 1 - 自上而下

    private void up2Down(int[] arr, int l, int r) {

        if(arr == null || l >= r) return;

        int m = (l + r) >> 1;

        up2Down(arr,l,m);

        up2Down(arr,m+1,r);

        merge(arr,l,m,r);

    }

    // 1 - 并操作

    private void merge(int[] arr, int l, int m, int r) {

        int i = l, j = m+1, k = 0;

        int[] t = new int[r-l+1];

        while(i <= m && j <= r) {

            if(arr[i] > arr[j]) t[k++] = arr[j++];

            else t[k++] = arr[i++];

        }

        while(i <= m) t[k++] = arr[i++];

        while(j <= r) t[k++] = arr[j++];

        for(int p = 0; p < k; p++) arr[l++] = t[p];

        t = null;

    }

}