快排

[ChrisLinn]

想请教一下，快排这么写可以么，比经典写法少用一个 swap ？

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);
    }
}

经典写法类似于

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

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);
    }
}

[testratter]

可以，只是代码上少一个 swap，实际运行的时候，迭代到最后一个元素，i=r 的时候，arr[i] <= pValue 永远为真，那个 swap 肯定会执行。
不过我觉得虽然省了一行，但代码明晰度下降了。
不过 i = l + 1 这个赋值在第一个元素小于 arr[r]的情况下会出错。