归并排序算法思想

采用分治的思想，将待排序数组划分成两部分，然后将子数组再次划分两份，知道数组大小是1，然后从下向上合并，合并的过程对数组进行排序，达到排序的目的。

归并排序算法流程

代码演示

升序

#include<iostream>#include<vector>using namespace std;void mergeSort(vector<int>& arr, int l, int r){	//base case	if (l == r) return;	int mid = l + (r - l) / 2;	//先递归	//左边数组完成排序	mergeSort(arr, l, mid);	//右边数组完成排序	mergeSort(arr, mid + 1, r);	//左右两边数组合并	int lp = l;	int rp = mid + 1;	//临时数组temp存放合并之后排序结果	vector<int> temp;	while (lp <= mid && rp <= r)	{		if(arr[lp] <= arr[rp])		{			temp.push_back(arr[lp++]);		}		else		{			temp.push_back(arr[rp++]);		}	}	//右边数组已经全部合并排序完成，左边数组有剩余元素带合并	while (lp <= mid)	{		temp.push_back(arr[lp++]);	}	//左边数组已经全部合并排序完成，右边数组有剩余元素带合并	while (rp <= r)	{		temp.push_back(arr[rp++]);	}	//将排好的临时数组的元素拷贝到数组中	for (int i = 0; i < temp.size(); i++)	{		arr[l + i] = temp[i];	}}int main(){	vector<int> arr = { 8,4,5,7,1,3,6,2 };	mergeSort(arr, 0, arr.size() - 1);	for (auto e : arr)	{		cout << e << " ";	}	return 0;}

运行结果：

降序

#include<iostream>#include<vector>using namespace std;//归并排序  降序void mergeSort(vector<int>& arr, int l, int r){	// base case 	if (l >= r) return;	int mid = l + (r - l) / 2;	mergeSort(arr, l, mid);	mergeSort(arr, mid + 1, r);		int lp = l;	int rp = mid + 1;	vector<int>temp;	while (lp <= mid && rp <= r)	{		if (arr[lp] >= arr[rp])		{			temp.push_back(arr[lp++]);		}		else		{			temp.push_back(arr[rp++]);		}	}	while (lp <= mid)	{		temp.push_back(arr[lp++]);	}	while (rp <= r)	{		temp.push_back(arr[rp++]);	}	for (int i = 0; i < temp.size(); i++)	{		arr[l + i] = temp[i];	}}int main(){	vector<int> arr = { 8,4,5,7,1,3,6,2 };	mergeSort(arr, 0, arr.size() - 1);	for (auto e : arr)	{		cout << e << " ";	}	return 0;}

运行结果：

算法特性

时间复杂度：O(N*logN)

空间复杂度：O(N)

稳定性：稳定