快速排序

(双指针加递归) $O(nlogn)$

时间复杂度

参考文献

C++ 代码

//用j做模板
void quick_sort(int arr[], int l, int r)
{
    if (l >= r) return;

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

//用i做模板

void quick_sort(int arr[], int l, int r)
{
    if (l >= r) return;
    //此处中间值尽量不取头尾,如果取中间的数则需要这样
    int i = l - 1, j = r + 1, x = arr[(l+r+1)/2];
    while (i < j)
    {
        do i ++ ; while (arr[i] < x);
        do j -- ; while (arr[j] > x);
        if (i < j) swap(arr[i], arr[j]);
    }
    //此处边界值需要注意
    quick_sort(arr, l, i-1), quick_sort(arr, i , r);
}


//写i-1  和 i 时  中间值不能取arr[l]  否则会死循环
//写j  和 j+1 时  中间值不能取arr[r]