#include <iostream>
using namespace std;
template <class T>void MSort(T a[], int left, int right){
if (left < right) {
int center = (left + right) /
 2;//取得中點
 //將原來序列分為兩段 MSort(a, left, center);
MSort(a, center+1, right);
 //合併剛才分開的兩段,得到原來序列的有序序列
Merge(a, left, center, right, right-left+1);
}}
template <class T>void MergeSort(T a[], int n){
 //調用遞迴歸併排序函數
MSort(a, 0, n-1);
}template <class T>void Merge(T a[], int left, int center, int right, int n){
 T *t = new T[n];
//存放被排序的元素
int i = left; int j = center + 1;
 int k = 0;
//合併陣列,用插入排序,如果左邊大就插入左邊的數,右邊的計數器等待,與下一個左邊的數比較;右邊大就插入右邊的數,左邊的計數器等待,與下一個右邊的數比較(這裡指的插入是插入到新陣列t[])
 while (i<=center && j<=right) {
 if (a[i] <= a[j]) t[k++] = a[i++];
 else t[k++] = a[j++];
}
//上面的步驟在執行完後,左或右邊都有可能剩餘若干個元素,而另一邊的元素肯定已全部複製到新陣列,這時需要特殊對待剩下的元素
 if (i == center+1) { while (j <= right) t[k++] = a[j++];
 } else {
 while (i <= center) t[k++] = a[i++];
 }
//把t[]的元素複製回a[]中left到right段
 for (i=left,k=0; i<=right; i++,k++) a[i] = t[k];
 //釋放記憶體
 delete []t;
}
int main(){
 int intArray[5] = { 5 , 6 , 2 , 5 , 9 };
 MergeSort(intArray,5);
 for(int i = 0; i < 5; i++) cout << intArray[i] << endl;} 
創作者介紹
創作者 shadow 的頭像
shadow

資訊園

shadow 發表在 痞客邦 留言(0) 人氣()