排序算法之归并排序(模板类)

#include<algorithm> using namespace std; template <class T> class element { public: element() { key = T(0);} ~element() {}; public: T key; }; #pragma once class merge_sort { public: merge_sort(void); ~merge_sort(void); // 排序算法 template <class T> void Sort(element<T> list[], int n); // 归并 template <class T> void Merge(element<T> list[], element<T> sorted[], int i, int m, int n); template <class T> void merge_pass(element<T> list[], element<T> sorted[], int n, int length); }; template <class T> void merge_sort::Sort(element<T> list[], int n) { int length = 1; element<T> *extra = new element<T>[2*n]; while(length < n) { merge_pass(list, extra, n , length); length *= 2; merge_pass(extra, list, n, length); length *= 2; } delete[]extra; } // 归并两个已经排序的表 // 将list[i],...,list[m] 和list[m+1],...,list[n]两个有序表归并为一个有序表(sorted[i],...,sorted[n]) template <class T> void merge_sort::Merge(element<T> list[], element<T> sorted[], int i, int m, int n) { // merge two sorted list files: list[i],...,list[m], \ // and obtain a sorted list: sorted[i],...,sorted[n] int j,k,t; j = m+1; // index for the second sublist k = i; while(i <= m && j <=n ) { if(list[i].key <= list[j].key) { sorted[k++] = list[i++]; } else { sorted[k++] = list[j++]; } } if(i > m) { for(t = j; t <= n; t++) { sorted[k+t-j] = list[t]; } } else { for(t = i; t <= m; t++) { sorted[k+t-i] = list[t]; } } } template <class T> void merge_sort::merge_pass(element<T> list[], element<T> sorted[], int n, int length) { int i = 0, j = 0; for(i = 0; i <= n-2*length; i += 2*length) { Merge(list, sorted, i, i+length-1, i+2*length-1); } if( i+length < n) { Merge(list, sorted, i, i+length-1, i+2*length-1); } else { for(j=i; j < n; j++) { sorted[j] = list[j]; } } }