归并排序是一种很重要的排序算法,体现的是分而治之的思想,很多的算法题的解法会借用这种算法思想,在这里使用C++编程实现归并排序,供自己回忆,供他人参考~
#include <bits/stdc++.h>
using namespace std;
// 合并(Merge)
void merge(vector<int> &vec, int start, int mid, int end) {
vector<int> temp; // 用来保存二路归并的临时结果
int i = start, j = mid + 1;
// 二路归并
while (i <= mid && j <= end) {
if (vec[i] < vec[j]) {
temp.push_back(vec[i++]);
} else {
temp.push_back(vec[j++]);
}
}
// 处理剩余的
while (i <= mid) temp.push_back(vec[i++]);
while (j <= end) temp.push_back(vec[j++]);
//重新赋值回去
for (int k = 0; k < temp.size(); k++) {
vec[start + k] = temp[k];
}
}
// mergeSort
void mergeSort(vector<int> &vec, int start, int end) {
// 递归出口
if (vec.empty() || start >= end) {
return;
}
// 二分
int mid = start + (end - start) / 2;
// 递归
mergeSort(vec, start, mid);
mergeSort(vec, mid + 1, end);
// 归并
merge(vec, start, mid, end);
}
int main() {
// 初始化一个待排序的向量
vector<int> vec = {1, 8, -6, 12, 5, 9};
// 调用自己写的快排
mergeSort(vec, 0, vec.size() - 1);
// 打印出排序之后的结果
for (auto x : vec) {
cout << x << ","; // -6,1,5,8,9,12,
}
return 0;
}