第四十九课归并排序和快速排序

归并示意图：

程序入下：

  1 #ifndef SORT_H
  2 #define SORT_H
  3 
  4 #include "Object.h"
  5 
  6 namespace DTLib
  7 {
  8 
  9 class Sort : public Object
 10 {
 11 private:
 12     Sort();
 13     Sort(const Sort&);
 14     Sort& operator = (const Sort&);
 15 
 16     template <typename T>
 17     static void Swap(T& a, T& b)
 18     {
 19         T c(a);
 20         a = b;
 21         b = c;
 22     }
 23 
 24     template < typename T >
 25     static void Merge(T src[], T helper[], int begin, int mid, int end, bool min2max=true)
 26     {
 27         int i = begin;
 28         int j = mid + 1;
 29         int k = begin;  //代表辅助空间起始位置
 30 
 31         while( (i <= mid) && (j <= end) )
 32         {
 33             if( min2max ? (src[i] < src[j]) : (src[i] > src[j]) )
 34             {
 35                 helper[k++] = src[i++];
 36             }
 37             else
 38             {
 39                 helper[k++] = src[j++];
 40             }
 41         }
 42 
 43         while( i <= mid)
 44         {
 45             helper[k++] = src[i++];
 46         }
 47 
 48         while( j <= end )
 49         {
 50             helper[k++] = src[j++];
 51         }
 52 
 53         for(i = begin; i <= end; i++)
 54         {
 55             src[i] = helper[i];
 56         }
 57     }
 58 
 59     template < typename T >
 60     static void Merge(T src[], T helper[], int begin, int end, bool min2max=true)
 61     {
 62         if( begin < end )
 63         {
 64             int mid = (begin + end) / 2;
 65 
 66             Merge(src, helper, begin, mid, min2max);
 67             Merge(src, helper, mid+1, end, min2max);
 68 
 69             Merge(src, helper, begin, mid, end, min2max); //真正的归并操作
 70         }
 71     }
 72 
 73 public:
 74     template < typename T >
 75     static void Select(T array[], int len, bool min2max=true)
 76     {
 77         for(int i = 0; i < len; i++)
 78         {
 79             int min = i;
 80             for(int j = i + 1; j < len; j++)
 81             {
 82                 if( min2max ? (array[min] > array[j]) : (array[min] < array[j]) )
 83                 {
 84                     min = j;
 85                 }
 86             }
 87 
 88             if( min != i)
 89             {
 90                 Swap(array[i], array[min]);
 91             }
 92         }
 93     }
 94 
 95     template < typename T >
 96     static void Insert(T array[], int len, bool min2max=true)
 97     {
 98         for(int i=1; i < len; i++)  //从1开始，第0个元素没有必要插入操作
 99         {
100             int k = i;
101             T e = array[i];
102 
103             for(int j=i-1; (j>=0) && (min2max ? (array[j] > e) : (array[j] < e)); j--)
104             {
105                 array[j+1] = array[j];
106                 k = j;
107             }
108 
109             if( k != i )   //赋值比“比较操作耗时”
110             {
111                 array[k] = e;
112             }
113         }
114     }
115 
116     template < typename T >
117     static void Bubble(T array[], int len, bool min2max=true)
118     {
119         bool exchange = true;
120 
121         for(int i=0; (i<len) && exchange; i++)
122         {
123             exchange = false;
124 
125             for(int j=len-1; j>i; j--)
126             {
127                 if(min2max ? (array[j] < array[j-1]) : (array[j] > array[j-1]))
128                 {
129                     Swap(array[j], array[j-1]);
130                     exchange = true;
131                 }
132             }
133         }
134     }
135 
136     template < typename T >
137     static void Shell(T array[], int len, bool min2max=true)
138     {
139         int d = len;
140         do
141         {
142             d = d / 3 + 1; //d的减小方式（实践证明这样做效果比较好）
143 
144             for(int i = d; i < len; i+=d)
145             {
146                 int k = i;
147                 T e = array[i];
148 
149                 for(int j=i-d; (j>=0) && (min2max ? (array[j] > e) : (array[j] < e)); j-=d)
150                 {
151                     array[j+d] = array[j];
152                     k = j;
153                 }
154 
155                 if( k != i )   //赋值比“比较操作耗时”
156                 {
157                     array[k] = e;
158                 }
159             }
160 
161         }while( d > 1 );
162     }
163 
164     template < typename T >
165     static void Merge(T array[], int len, bool min2max=true)
166     {
167         T* helper = new T[len];
168 
169         if( helper != NULL )
170         {
171             Merge(array, helper, 0, len - 1, min2max);
172         }
173 
174         delete[] helper;
175     }
176 };
177 
178 }
179 
180 #endif // SORT_H

注意：归并排序是一种稳定的排序算法

图解：

代码如下：

  1 #ifndef SORT_H
  2 #define SORT_H
  3 
  4 #include "Object.h"
  5 
  6 namespace DTLib
  7 {
  8 
  9 class Sort : public Object
 10 {
 11 private:
 12     Sort();
 13     Sort(const Sort&);
 14     Sort& operator = (const Sort&);
 15 
 16     template <typename T>
 17     static void Swap(T& a, T& b)
 18     {
 19         T c(a);
 20         a = b;
 21         b = c;
 22     }
 23 
 24     template < typename T >
 25     static void Merge(T src[], T helper[], int begin, int mid, int end, bool min2max=true)
 26     {
 27         int i = begin;
 28         int j = mid + 1;
 29         int k = begin;  //代表辅助空间起始位置
 30 
 31         while( (i <= mid) && (j <= end) )
 32         {
 33             if( min2max ? (src[i] < src[j]) : (src[i] > src[j]) )
 34             {
 35                 helper[k++] = src[i++];
 36             }
 37             else
 38             {
 39                 helper[k++] = src[j++];
 40             }
 41         }
 42 
 43         while( i <= mid)
 44         {
 45             helper[k++] = src[i++];
 46         }
 47 
 48         while( j <= end )
 49         {
 50             helper[k++] = src[j++];
 51         }
 52 
 53         for(i = begin; i <= end; i++)
 54         {
 55             src[i] = helper[i];
 56         }
 57     }
 58 
 59     template < typename T >
 60     static void Merge(T src[], T helper[], int begin, int end, bool min2max)
 61     {
 62         if( begin < end )
 63         {
 64             int mid = (begin + end) / 2;
 65 
 66             Merge(src, helper, begin, mid, min2max);
 67             Merge(src, helper, mid+1, end, min2max);
 68 
 69             Merge(src, helper, begin, mid, end, min2max); //真正的归并操作
 70         }
 71     }
 72 
 73     template < typename T >
 74     static int Partition(T array[], int begin, int end, bool min2max)
 75     {
 76         T pv = array[begin];
 77 
 78         while( begin < end )
 79         {
 80             while( (begin < end) && (min2max ? (array[end] > pv) : (array[end] < pv)) )
 81             {
 82                 end--;
 83             }
 84 
 85             Swap(array[begin], array[end]);
 86 
 87             while( (begin < end) && (min2max ? (array[begin] <= pv) : (array[begin] >= pv)) )
 88             {
 89                 begin++;
 90             }
 91 
 92             Swap(array[begin], array[end]);
 93         }
 94 
 95         array[begin] = pv;  //基准就位
 96 
 97         return begin;
 98     }
 99 
100     template < typename T >
101     static void Quick(T array[], int begin, int end, bool min2max)
102     {
103         if( begin < end )
104         {
105             int pivot = Partition(array, begin, end, min2max);
106 
107             Quick(array, begin, pivot - 1, min2max);
108             Quick(array, pivot + 1, end, min2max);
109         }
110     }
111 
112 public:
113     template < typename T >
114     static void Select(T array[], int len, bool min2max=true)
115     {
116         for(int i = 0; i < len; i++)
117         {
118             int min = i;
119             for(int j = i + 1; j < len; j++)
120             {
121                 if( min2max ? (array[min] > array[j]) : (array[min] < array[j]) )
122                 {
123                     min = j;
124                 }
125             }
126 
127             if( min != i)
128             {
129                 Swap(array[i], array[min]);
130             }
131         }
132     }
133 
134     template < typename T >
135     static void Insert(T array[], int len, bool min2max=true)
136     {
137         for(int i=1; i < len; i++)  //从1开始，第0个元素没有必要插入操作
138         {
139             int k = i;
140             T e = array[i];
141 
142             for(int j=i-1; (j>=0) && (min2max ? (array[j] > e) : (array[j] < e)); j--)
143             {
144                 array[j+1] = array[j];
145                 k = j;
146             }
147 
148             if( k != i )   //赋值比“比较操作耗时”
149             {
150                 array[k] = e;
151             }
152         }
153     }
154 
155     template < typename T >
156     static void Bubble(T array[], int len, bool min2max=true)
157     {
158         bool exchange = true;
159 
160         for(int i=0; (i<len) && exchange; i++)
161         {
162             exchange = false;
163 
164             for(int j=len-1; j>i; j--)
165             {
166                 if(min2max ? (array[j] < array[j-1]) : (array[j] > array[j-1]))
167                 {
168                     Swap(array[j], array[j-1]);
169                     exchange = true;
170                 }
171             }
172         }
173     }
174 
175     template < typename T >
176     static void Shell(T array[], int len, bool min2max=true)
177     {
178         int d = len;
179         do
180         {
181             d = d / 3 + 1; //d的减小方式（实践证明这样做效果比较好）
182 
183             for(int i = d; i < len; i+=d)
184             {
185                 int k = i;
186                 T e = array[i];
187 
188                 for(int j=i-d; (j>=0) && (min2max ? (array[j] > e) : (array[j] < e)); j-=d)
189                 {
190                     array[j+d] = array[j];
191                     k = j;
192                 }
193 
194                 if( k != i )   //赋值比“比较操作耗时”
195                 {
196                     array[k] = e;
197                 }
198             }
199 
200         }while( d > 1 );
201     }
202 
203     template < typename T >
204     static void Merge(T array[], int len, bool min2max=true)
205     {
206         T* helper = new T[len];
207 
208         if( helper != NULL )
209         {
210             Merge(array, helper, 0, len - 1, min2max);
211         }
212 
213         delete[] helper;
214     }
215 
216     template < typename T >
217     static void Quick(T array[], int len, bool min2max=true)
218     {
219         Quick(array, 0, len - 1, min2max);
220     }
221 };
222 
223 }
224 
225 #endif // SORT_H

注意：快速排序是一种不稳定的排序算法

小结：

第四十九课 归并排序和快速排序

第四十九课归并排序和快速排序