堆排序--模版类

今天闲来没事干，写个堆排序，用模版类实现的，数据可是任何可比较的类型。代码如下：

数据结构模版类：

MySqList.h

  1 #ifndef __MYSQLIST
  2 #define __MYSQLIST
  3 template <typename Type>
  4 class MySqList
  5 {
  6 private:
  7     int len;
  8     Type* data;
  9 public:
 10     MySqList();
 11     MySqList(const MySqList<Type> *t);
 12     MySqList(int n, const Type* arr);
 13     const int Len();
 14     Type* Data();
 15     void swap(int ind1, int ind2);
 16     const Type get(int ind);
 17     void set(int ind, Type v);
 18     void showdata();
 19     ~MySqList();
 20 };
 21 
 22 
 23 template <typename Type>
 24 MySqList<Type>::MySqList()
 25 {
 26     len = 10;
 27     data = new Type[len];
 28 }
 29 
 30 template <typename Type>
 31 MySqList<Type>::MySqList(const MySqList<Type> *t)
 32 {
 33     if(this != t)
 34     {
 35         len = t->len;
 36         data = new Type[len+1];
 37         for(int i=0;i<len;i++)
 38             data[i] = t->data[i];
 39         data[len] = 0;
 40     }
 41 }
 42 
 43 template <typename Type>
 44 MySqList<Type>::MySqList(int n, const Type* arr)
 45 {
 46     len = n;
 47     if(data != arr)
 48     {
 49         data = new Type[len+1];
 50     }
 51     for(int i=0;i<n;i++)
 52         data[i] = arr[i];
 53     data[len]=0;
 54 }
 55 
 56 template <typename Type>
 57 MySqList<Type>::~MySqList()
 58 {
 59     delete[] data;
 60     data = 0;
 61 }
 62 
 63 
 64 template <typename Type>
 65 Type* MySqList<Type>::Data()
 66 {
 67     return data;
 68 }
 69 
 70 template <typename Type>
 71 const int MySqList<Type>::Len()
 72 {
 73     return len;
 74 }
 75 
 76 template <typename Type>
 77 const Type MySqList<Type>::get(int ind)
 78 {
 79     return data[ind];
 80 }
 81 
 82 template <typename Type>
 83 void MySqList<Type>::set(int ind, Type v)
 84 {
 85     data[ind] = v;
 86 }
 87 
 88 template <typename Type>
 89 void MySqList<Type>::swap(int ind1, int ind2)
 90 {
 91     Type temp = data[ind1];
 92     data[ind1] = data[ind2];
 93     data[ind2] = temp;
 94 }
 95 
 96 template <typename Type>
 97 void MySqList<Type>::showdata()
 98 {
 99     for(int i=0; i<len-1; i++)
100         cout<<data[i]<<" ";
101     cout<<data[len-1]<<endl;
102 }
103 #endif

View Code

堆排序模版函数：

HeapSort.h

 1 #include "MySqList.h"
 2 
 3 template <typename Type>
 4 void HeapSort(MySqList<Type>* L)
 5 {
 6     for(int i = (L->Len()-1)/2; i>=0; i--)
 7         HeapAdjust(L, L->Len(), i);
 8     for(int i=L->Len()-1; i>=0; i--)
 9     {
10         L->swap(0, i);
11         HeapAdjust(L, i, 0);
12     }
13 }
14 
15 template <typename Type>
16 void HeapAdjust(MySqList<Type>* L, int n, int i)
17 {
18     int temp, s;
19     temp = L->get(i);
20     for(s=2*i+1; s<n; s = s*2+1)
21     {
22         if(s<n-1 && L->get(s) < L->get(s+1))
23         {
24             s++;
25         }
26         if(temp >= L->get(s))
27         {
28             break;
29         }
30         L->swap(i,s);
31         i = s;
32     }
33 }

View Code

欢迎各位来喷。