归并排序


		归并排序
归并（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++ ,