[数据结构与算法]归并排序算法

分治策略

(1) 分解：将原问题分解成若干个规模较小，相互独立的小问题，这些小问题与原问题相同

(2) 求解：求解小问题(很容易求解)

(3) 合并：将小问题的解合并成原问题的解

归并排序采用分治策略进行排序(以升序为例)

?? ? ? ?? ?

#include<iostream>
using namespace std;
#include "IO.h" //处理输入输出
#include<vector>
//以升序为例   小 --> 大
//全局域
	vector<int> nums; //待排序组
	vector<int> temp; //临时的已排序组，归并过程中，依次放入排序结果

//归并过程  low++    mid     high++
void merge( int low, int mid, int high)
{
	int i = low;    //i遍历左半部分
	int j = mid + 1; //j遍历右半部分
	int k = low;  //遍历临时数组

	while (i <= mid && j <= high)
	{
		//选择较小的元素，依次放入临时数组里
		if (nums[i] < nums[j]) 
		{
			temp[k] = nums[i];
			k++;  // k遍历temp
			i++; 
		}
		else
		{
			temp[k] = nums[j];
			k++;  
			j++;
		}		
	}
	//左半部分还有剩余，右半部分已遍历完
	while (i <= mid)
	{
		temp[k] = nums[i];
		k++;
		i++;
	}

	//左半部分已遍历完，右半部分还有剩余
	while (j <= high)
	{
		temp[k] = nums[j];
		k++;
		j++;
	}
	//将临时数组，拷贝给原数组
	nums = temp;

}

//归并排序
void mergeSort( int i, int j)
{
	if (i >= j) //递归出口
		return;
	
	//分解，每次分两部分
	int mid = (i + j) / 2;
	mergeSort(i,mid);  //对左半部分进行排序
	mergeSort(mid+1,j); //对右半部分进行归并排序
	//合并
	merge(i, mid, j);
}

int main()
{	
	nums = inputNum(); //输入一组数，存放在nums中
	temp = nums;   //临时数组temp与nums一样大
	
	int len = nums.size();
	mergeSort(0, len-1);
	printArray(nums); //输出排序后的数组

	system("pause");
	return 0;
}