合并排序
std::vector<int> temp;
void merge(std::vector<int>& arr, int l, int mid, int r) {
std::copy(arr.begin() + l, arr.begin() + r, temp.begin() + l);
int p = l, q = mid;
for (int i = l; i < r; i++) {
if (q >= r || (p < mid && arr[p] < arr[q])) {
temp[i] = arr[p++];
} else {
temp[i] = arr[q++];
}
}
std::copy(temp.begin() + l, temp.begin() + r, arr.begin() + l);
}
void mergeSort(std::vector<int>& arr, int l, int r) {
if (r - l == 1) {
return ;
}
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid, r);
merge(arr, l, mid, r);
}
void mergeSort(std::vector<int>& arr) {
temp.resize(arr.size());
mergeSort(arr, 0, (int) arr.size());
}
最后更新:
2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42