基本排序算法

  1 typedef int datatype;
  2 
  3 inline void swap(datatype &a, datatype &b)
  4 {
  5     datatype tmp = a;
  6     a = b;
  7     b = tmp;
  8 }
  9 
 10 /***********************************
 11   冒泡排序:
 12   每次将最小的数"冒"在最前面 
 13 ***********************************/
 14 void BubbleSort(datatype Array[], int length)
 15 {
 16     for (int i = 0; i < length; i++)
 17     {
 18         for (int j = i+1; j < length; j++)
 19         {
 20             if (Array[j] < Array[i])
 21             {
 22                 swap(Array[i], Array[j]);
 23             }
 24         }
 25     }
 26 }
 27 
 28 /*********************************** 
 29  插入排序
 30    从后往前依次插入元素 
 31 ***********************************/
 32 void InsertSort(datatype Array[], int length)
 33 {
 34 
 35     for(int j = 1; j  != length; j++)  
 36     {  
 37         datatype key = Array[j];  
 38         int i = j - 1;  
 39         while(i != -1 && Array[i] > key)  
 40         {  
 41             Array[i+1]= Array[i];  
 42             i--;  
 43         }  
 44          
 45         Array[i+1] = key;  
 46     }  
 47 
 48 }
 49 
 50 /*********************************** 
 51  归并排序
 52    分别对左右两边进行排序,然后合并,需要申请新的空间 
 53 ***********************************/ 
 54 static void Merge(datatype SortArray[], int start, int middle, int end)  
 55 {  
 56     int LeftLength = middle - start + 1;  
 57     int RightLength = end - middle;  
 58   
 59     // 创建临时数组保存已排序好的左右数组   
 60     datatype *LeftArray = (datatype *)malloc(LeftLength * sizeof(datatype));  
 61     for(int i = 0; i != LeftLength; ++i)  
 62         LeftArray[i] = SortArray[start + i];  
 63     datatype *RightArray = (datatype *)malloc(RightLength * sizeof(datatype));  
 64     for(int i = 0; i != RightLength; ++i)  
 65         RightArray[i] = SortArray[middle + i + 1];  
 66  
 67     // 归并   
 68     int i = 0;  
 69     int j = 0;  
 70     int k = start;  
 71     while(i != LeftLength && j != RightLength)  
 72     {  
 73         if(LeftArray[i] <= RightArray[j])  
 74             SortArray[k++] = LeftArray[i++];  
 75         else  
 76             SortArray[k++] = RightArray[j++];  
 77     }  
 78   
 79     while(i != LeftLength)  
 80     {  
 81         SortArray[k++] = LeftArray[i++];      
 82     }  
 83   
 84     while(j != RightLength)  
 85     {  
 86         SortArray[k++] = RightArray[j++];  
 87     }  
 88   
 89     free(LeftArray);  
 90     free(RightArray);  
 91 }  
 92 
 93 static void _MergeSort(datatype Array[], int start, int end)
 94 {
 95     if (start < end)
 96     {
 97         int middle = (start + end)/2;
 98         _MergeSort(Array, start, middle);
 99         _MergeSort(Array, middle+1, end);
100         Merge(Array, start, middle, end);
101     }
102 }
103 
104 void MergeSort(datatype Array[], int length)
105 {
106     _MergeSort(Array, 0, length -1);
107 }
108 
109 /*********************************** 
110     快速排序算法,和归并排序相比,快速排序不需要额外的空间
111 ***********************************/
112 // 将数组划分为2组,左边的都比中间元素小,右边的都比中间元素大
113 static int Partition(datatype SortArray[], int start, int end)  
114 {  
115     datatype middleValue = SortArray[end];  
116     int middleIndex = start - 1;  
117   
118    for(int j = start; j != end; ++j)  
119     {  
120         if (SortArray[j] <= middleValue)  
121         {  
122           middleIndex++;  
123            swap(SortArray[middleIndex], SortArray[j]);  
124         }  
125           
126     }  
127     swap(SortArray[middleIndex+1], SortArray[end]);  
128   
129     return middleIndex+1;  
130 }  
131 
132 static void _QuickSort(datatype SortArray[], int start, int end)  
133 {  
134     if(start < end)  
135     {  
136         int middle = Partition(SortArray, start, end);  
137         _QuickSort(SortArray, start, middle-1);  
138         _QuickSort(SortArray, middle+1, end);  
139     }  
140 }  
141 
142 void QuickSort(datatype SortArray[], int length)
143 {
144     _QuickSort(SortArray, 0, length-1);    
145 }
146 
147 /*********************************** 
148  计数排序 
149     计数排序的基本思想是对每一个输入元素x,确定 
150  出不小于x的元素个数。 
151     只适用于正整数 
152 ***********************************/
153 static void _CountingSort(datatype SortArray[], datatype SortedArray[], int ArrayLength,datatype maxValue)  
154 {  
155     datatype *CountArray  = (datatype *)malloc((maxValue+1) * sizeof(datatype)); 
156     assert(NULL != CountArray);
157   
158     // 初始化   
159     for(int i = 0; i != maxValue+1; ++i)  
160         CountArray[i] = 0;  
161   
162     // 计数   
163     for(int i = 0; i != ArrayLength; ++i)  
164         CountArray[(SortArray[i])] += 1;    // 等于的元素个数   
165   
166     /*
167        若不考虑稳定性,可以使用以下代码,此时实际不需要SortedArray数组
168         int index = 0;
169         for (datatype i = 0; i <= maxValue; i++)
170         {
171             for (int j = 0; j < CountArray[i]; j++)
172             {
173                 SortedArray[inddex++] = i; 
174             }
175         }
176 
177     */
178     
179     // 重排   
180     /* 
181     从大到小,可保持稳定性,即具有相同值的元素 
182     在输出数组中的相对次序与他们在输入数组中的次序相同 
183     */  
184     for(int i = 1; i != maxValue+1; ++i)  
185         CountArray[i] += CountArray[i-1];   // 小于或等于的个数   
186    
187     for(int i = ArrayLength-1; i != -1; --i)  
188     {  
189         // CountArray[SortArray[i]]：小于或等于SortArray[i]的个数,再-1即为排序后在数组中的位置
190         SortedArray[(CountArray[(SortArray[i])]) - 1] = SortArray[i];   
191         CountArray[(SortArray[i])] -= 1;  
192           
193     }  
194   
195     free(CountArray);  
196 }  
197 
198 void CountingSort(datatype SortArray[], int length)
199 {
200     datatype maxValue = 0;
201     for (int i = 0; i < length; i++)
202     {
203         maxValue = maxValue > SortArray[i] ? maxValue : SortArray[i];
204     }
205 
206     datatype *SortedArray = (datatype *)malloc(length * sizeof(datatype));
207     assert(NULL !=SortedArray);
208 
209     _CountingSort(SortArray, SortedArray, length, maxValue);
210 
211     for (int i = 0; i < length; i++)
212     {
213         SortArray[i] = SortedArray[i];
214     }
215 
216     free(SortedArray);
217 
218 }
219 
220 /***********************************
221  基数排序 
222     利用计数排序算法,对数组从低向高位排序 
223 ***********************************/
224 static void CountingSortForRadixSort(datatype SortArray[], datatype CmpArray[], int ArrayLength, int maxValue)  
225 {  
226     datatype *CountArray  = (datatype *)malloc((maxValue+1) * sizeof(datatype));  
227     datatype *SortedArray = (datatype *)malloc(ArrayLength * sizeof(datatype));  
228     assert(NULL != CountArray || NULL != SortedArray);
229 
230     for(int i = 0; i != maxValue+1; ++i)  
231         CountArray[i] = 0;  
232       
233     for(int i = 0; i != ArrayLength; ++i)  
234         CountArray[(CmpArray[i])]++;  
235     for(int i = 1; i != maxValue+1; ++i)  
236         CountArray[i] += CountArray[i-1];  
237   
238     for(int i = ArrayLength-1; i != -1; --i)  
239     {  
240         SortedArray[(CountArray[CmpArray[i]])-1]= SortArray[i];  
241         CountArray[CmpArray[i]] -= 1;  
242     }  
243   
244     for(int i = 0; i != ArrayLength; ++i)  
245         SortArray[i] = SortedArray[i];  
246   
247     free(CountArray);  
248     free(SortedArray);  
249       
250 }  
251 
252 void RadixSort(datatype SortArray[], int ArrayLength)  
253 {  
254     datatype *RadixArray = (datatype *)malloc(ArrayLength * sizeof(datatype)); 
255     assert(NULL != RadixArray);
256      
257     datatype BaseNumber = 1;  
258     bool rsIsOk = false;  
259   
260     while(false ==rsIsOk)  
261     {  
262         rsIsOk = true;  
263         BaseNumber *= 10;  
264   
265         for(int i = 0; i != ArrayLength; ++i)  
266         {  
267             RadixArray[i] = SortArray[i] % BaseNumber;  
268             RadixArray[i] = RadixArray[i] / (BaseNumber / 10);  
269             if(RadixArray[i] > 0)  
270                 rsIsOk = false;  
271         }  
272         if(true == rsIsOk)  
273             break;  
274         CountingSortForRadixSort(SortArray, RadixArray, ArrayLength, 9);  
275     }  
276   
277     free(RadixArray);  
278 }  
279 /***********************************
280 堆排序算法 
281     堆: 可以视为一棵完全二叉树,树的每一层都是填满的,除了最后一层 
282     其任何一非叶节点满足性质：
283     Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
284 
285     堆排序算法主要用于优先级队列 
286 ***********************************/
287 #define PARENT(x)   ((x) >> 1)            // 节点x的父节点下标号   
288 #define LEFT(x)     ((x) << 1)            // 节点x的左子节点下标号   
289 #define RIGHT(x)    (((x) << 1) + 1)      // 节点x的右子节点下标号   
290   
291 static void MaxHeapify(int SortArray[], int heap_size, int parent)  
292 {   
293     int left, right, largest;  
294   
295     left = LEFT(parent+1) - 1;  
296     right = RIGHT(parent+1) -1;  
297   
298     if(left < heap_size && SortArray[left] > SortArray[parent])  
299         largest = left;  
300     else  
301         largest = parent;  
302   
303     if(right < heap_size && SortArray[right] > SortArray[largest])  
304         largest = right;  
305   
306     if(largest != parent)  
307     {  
308         swap(SortArray[largest], SortArray[parent]);  
309   
310         MaxHeapify(SortArray, heap_size, largest);  
311     }  
312 }  
313 
314 static void BuildMaxHeap(int SortArray[], int ArrayLength)  
315 {  
316     int HeapSize = ArrayLength;  
317   
318     for(int i = ArrayLength/2; i != -1; --i)  
319         MaxHeapify(SortArray,HeapSize,i);  
320 } 
321 
322 void HeapSort(int SortArray[], int ArrayLength)  
323 {  
324     int HeapSize = ArrayLength;  
325   
326     BuildMaxHeap(SortArray, ArrayLength);  
327     for(int i = ArrayLength-1; i !=0; --i)  
328     {  
329         swap(SortArray[0], SortArray[i]);  
330         HeapSize--;  
331         MaxHeapify(SortArray, HeapSize, 0);  
332     }  
333 }