/*
6.快速排序
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(nlogn)　
*/
void quickSort(int* arrays, int l, int r) {
    if(l < r) {
        int i = l, j = r, x = arrays[i];
        while(i < j) {

            while(i < j && arrays[j] >= x) { // 从右向左找第一个小于x的数
                j--;
            }
            if(i < j) {
                arrays[i++] = arrays[j];
            }

            while(i < j && arrays[i] < x) { // 从左向右找第一个大于等于x的数
                i++;
            }
            if(i < j) {
                arrays[j--] = arrays[i];
            }
        }
        arrays[i] = x;
        quickSort(arrays, l, i - 1); // 递归调用
        quickSort(arrays, i + 1, r);
    }
}