想请教一下,快排这么写可以么,比经典写法少用一个 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
testratter 2018-02-23 13:25:24 +08:00 via Android
可以,只是代码上少一个 swap,实际运行的时候,迭代到最后一个元素,i=r 的时候,arr[i] <= pValue 永远为真,那个 swap 肯定会执行。
不过我觉得虽然省了一行,但代码明晰度下降了。 不过 i = l + 1 这个赋值在第一个元素小于 arr[r]的情况下会出错。 |