堆排序

 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 #endif

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

 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 }