快速排序
int partition(std::vector<int>& arr, int l, int r) {
int pivot = arr[l];
while (l < r) {
while (l < r && arr[r] >= pivot) r--;
arr[l] = arr[r];
while (l < r && arr[l] <= pivot) l++;
arr[r] = arr[l];
}
arr[l] = pivot;
return l;
}
void quickSort(std::vector<int>& arr, int l, int r) {
if (l < r) {
// random select pivot, can reduce the probability of the worst case complexity
int i = rand() % (r - l + 1) + l;
std::swap(arr[l], arr[i]);
int pos = partition(arr, l, r);
quickSort(arr, l, pos - 1);
quickSort(arr, pos + 1, r);
}
}
void quickSort(std::vector<int>& arr) {
srand((unsigned)time(NULL));
quickSort(arr, 0, (int) arr.size() - 1);
}
最后更新:
2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42