归并排序
归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
排序思想：
将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
重复上述步骤，直到所有元素排序完毕
C++实现：
[cpp]
/****************************
*Name:归并排序_递归.cpp
*Tags:排序 递归 归并
*Note:
*****************************/
#include<iostream>
#define MAX_SIZE1000
using namespacestd;
template<typename Type> void MergeSort(Type *, int, int);
template<typename Type> void Merge(Type *, int, int, int);
int main()
{
int len, i, array[MAX_SIZE];
cout << "Input the Size of thearray: ";
cin >> len;
for(i = 0; i < len; i++) {
cin>> array[i];
}
MergeSort(array, 0, len-1); //归并操作
cout << "After Sort: "<< endl;
for(i = 0; i < len; i++) {
cout<< array[i] << " ";
}
cout << endl;
return 0;
}
template<typename Type>
voidMergeSort(Type *array, int start, int end)
{
if(start < end) {
intmiddle = (start + end) / 2;
MergeSort(array, start, middle); //归并排序
MergeSort(array, middle+1, end);
Merge(array, start, middle, end); //归并操作
}
}
template<typename Type>
void Merge(Type*array, int start, int middle, int end)
{
int i, j, t;
Type *temp = new Type[end-start+1];
i = start;
j = middle+1;
t = 0;
while(i <= middle && j <=end) {
if(array[i] < array[j]) {
temp[t++] = array[i];
i++;
}else {
temp[t++] = array[j];
j++;
}
}
while(i <= middle) {
temp[t++] = array[i++];
}
while(j <= end) {
temp[t++] = array[j++];
} //归并过程
for(i = 0; i < t; i++) {
array[i+start] = temp[i];
}
delete [] temp;
}
归并排序的速度次于快速排序，但是它是一个稳定的排序算法。归并排序的时间复杂度为O(nlogn)，它的最好，最坏，平均时间复杂度一样，空间复杂度为O(n)，主要是在归并操作时需要额外的空间。
补充：软件开发 , C++ ,
