快排这么写有错不

V2EX = way to explore

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

现在注册

已注册用户请登录

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

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

4 条回复 • 2018-01-24 10:51:42 +08:00