基础算法复习之二：归并排序

归并排序是稳定排序，且其最好，最坏，平均时间复杂度均为O(nlogn)；

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//快速排序
void merge(vector<int>& nums, int low, int mid, int high, vector<int> temp)//nums一定是引用，不然排序后返回的还是原来的顺序
{
	int k = 0;
	int i = low;
	int j = mid + 1;
	while (i <= mid && j <= high)
	{
		if (nums[i] <= nums[j])
			temp[k++] = nums[i++];
		else
			temp[k++] = nums[j++];
	}
	while(i<=mid)  //后半部分已经遍历完，前半部分还有
		temp[k++] = nums[i++];
	while (j<=high)//前半部分已经遍历完，后半部分还有
		temp[k++] = nums[j++];
	for (int i = 0; i < k; i++) //这一步一定要写，将有序的数组写回nums
		nums[low + i] = temp[i];
}
void mergesort(vector<int> &nums, int low, int high, vector<int> temp)
{
	if (low < high)
	{
		int mid = (low + high) >> 1;
		mergesort(nums, low, mid, temp);//前半部分有序
		mergesort(nums, mid + 1, high, temp);//后半部分有序
		merge(nums, low, mid, high, temp);//对两个已经有序的子部分进行合并；
	}
}

int main()
{
	vector<int>  nums{1,4,2,3,5,9,8,6,7,0,10,14,23,20,19,68};
	vector<int> res(nums.size());
	mergesort(nums,0,nums.size()-1,res);
	return 0;
}