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);
}
}
1
ConradG 2018-01-22 16:56:46 +08:00
第一个是错的,以 pValue 为界左小右大的性质不能保持。
|