快排这么写有错不

[ChrisLinn]

int partition(int arr[], int l, int r) {
    int pPos = l, pValue = arr[l];
    for (int i = l+1; i <= r; ++i)
        if (arr[i] <= pValue) std::swap(arr[i], arr[pPos++]);
    return pPos;
}

void quicksort(int arr[], int l, int r) { 
    if (l < r) {
        int pivot = partition(arr, l, r);
        quicksort(arr, l, pivot-1);
        quicksort(arr, pivot+1, r);
    }
}

比经典写法少用一个 swap ？

int partition(int arr[], int l, int r) {
    int pPos = l, pValue = arr[r];
    for (int i = l; i < r; ++i)
        if (arr[i] <= pValue) std::swap(arr[i], arr[pPos++]);
    std::swap(arr[pPos], arr[r]);
    return pPos;
}

void quicksort(int arr[], int l, int r) { 
    if (l < r) {
        int pivot = partition(arr, l, r);
        quicksort(arr, l, pivot-1);
        quicksort(arr, pivot+1, r);
    }
}

[ConradG]

第一个是错的，以 pValue 为界左小右大的性质不能保持。

[ChrisLinn]

@ConradG 可不可以给个 case 谢谢，我设计的几个 case 都正确排序了

[ConradG]

@ChrisLinn [2,4,1,3]

[ChrisLinn]

@ConradG xiexie~