归并排序

思路：（分而治之的思想）

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4.重复步骤 3 直到某一指针达到序列尾；

5.将另一序列剩下的所有元素直接复制到合并序列尾。

代码实现：

#include <iostream>

using namespace std;

template <typename T> //整數或浮點數皆可使用

void merge(T* data, int start, int mid, int end, T* result)

{

	int i, j, k;

	i = start;

	j = mid + 1;                        //避免重复比较data[mid]

	k = 0;

	while (i <= mid && j <= end)        //数组data[start,mid]与数组(mid,end]均没有全部归入数组result中去

	{

		if (data[i] <= data[j])         //如果data[i]小于等于data[j]

			result[k++] = data[i++];    //则将data[i]的值赋给result[k]，之后i,k各加一，表示后移一位

		else

			result[k++] = data[j++];    //否则，将data[j]的值赋给result[k]，j,k各加一

	}

	while (i <= mid)                    //表示数组data(mid,end]已经全部归入result数组中去了，而数组data[start,mid]还有剩余

		result[k++] = data[i++];        //将数组data[start,mid]剩下的值，逐一归入数组result

	while (j <= end)                    //表示数组data[start,mid]已经全部归入到result数组中去了，而数组(mid,high]还有剩余

		result[k++] = data[j++];        //将数组a[mid,high]剩下的值，逐一归入数组result

	for (i = 0; i < k; i++)             //将归并后的数组的值逐一赋给数组data[start,end]

		data[start + i] = result[i];    //注意，应从data[start+i]开始赋值

};

template <typename T>

void merge_sort(T* data, int start, int end, T* result)

{

	if (start < end)

	{

		int mid = start + (end - start) / 2;

		merge_sort(data, start, mid, result);                    //对左边进行排序

		merge_sort(data, mid+1, end, result);                    //对右边进行排序

		merge(data, start, mid, end, result);                    //把排序好的数据合并

	}

};

int main(){

	int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };

	int temp[11] = {0};

	int step[] = { 5 , 3, 1 };

	int len = (int) sizeof(arr) / sizeof(*arr);

	int steplen = (int) sizeof(step) / sizeof(*step);

	merge_sort(arr,0, 10, temp);

	for (int i = 0; i < len; i++)

		cout << arr[i] << ' ';

	cout << endl;

	double arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };

	len = (int) sizeof(arrf) / sizeof(*arrf);

	double temp1[14];

	merge_sort(arrf, 0, 13, temp1);

	for (int i = 0; i < len; i++)

		cout << arrf[i] << ' ' << endl;

	return 0;

};

十大经典排序之归并排序（C++实现）的相关教程结束。