【Algorithms】归并排序(merge sort)

时间:2023-06-03 14:05:08

几个比较常见的排序算法里头,这个我是比较生疏的一个,有一天突然被问了一个问题是,归并排序最大的特点是什么,我才想起这个算法来。下午又看不进书啦,就实现一下,记下来。

归并排序采取的是分治策略,就是先将数据不断地进行二分,然后分别排序子序列之后再不断地合并在一起。

归并排序与快排一样,时间复杂度是O(nlogn),是一个比较高效率的排序算法。

【Algorithms】归并排序(merge sort)

vector<int> mergeSort(vector<int>& nums, int m, int n) {
if (m == n) return{ nums[n] };
int mid = m + (n - m) / ;
vector<int> left = mergeSort(nums, m, mid);
vector<int> right = mergeSort(nums, mid + , n); int i = ;
int j = ;
vector<int> merge;
while (i < left.size() || j < right.size()) {
if (j >= right.size() || i < left.size() && left[i] < right[j]) {
merge.push_back(left[i]);
i++;
}
else if (j < right.size()) {
merge.push_back(right[j]);
j++;
}
}
return merge;
}