快速排序-JZTXT

　　没想到再次回顾快排发现自己对于快排的理解还不是很深入。

　　快排的时间复杂度为O(nlogn) ~ O(n^2);

若用《数据结构（C语言版）》中的算法：

void Quick_Sort(int *arr, int begin, int end){
    if(begin > end)
        return;
    int tmp = arr[begin];
    int i = begin;
    int j = end;
    while(i != j){
        while(arr[j] >= tmp && j > i)
            j--;
        while(arr[i] <= tmp && j > i)
            i++;
        if(j > i){
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);
    Quick_Sort(arr, i+1, end);
}

每次以第一个数据为参照数，则在数组为逆序时的时间复杂度为O(n^2)，递归次数为n-1，而最好的时候（平均递归），递归次数为logn，每次遍历次数都为n。

　　但是这样子写，在Acwing会被卡，所以有了优化代码：

void quick_sort(int f[],int l, int r)
{
    if(l >= r) return;
    
    int i = l - 1, j = r + 1, x = f[l + r >> 1];
    while(i < j)
    {
        do i ++; while (f[i] < x);
        do j --; while (f[j] > x);
        if(i < j) swap(f[i],f[j]);
    }
    
    quick_sort(f , l, j);
    quick_sort(f , j + 1, r);
}

这里面的参照数是随机选取的（取的数组中心值），所以在最坏情况下的时间复杂度要小于O(n²)。