快排 - V2EX

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2503 天前的主题，其中的信息可能已经有所发展或是发生改变。

想请教一下，快排这么写可以么，比经典写法少用一个 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);
    }
}

1 条回复 • 2018-02-23 13:25:24 +08:00

testratter

2018-02-23 13:25:24 +08:00 via Android

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