[数据结构与算法] : 排序

              1
            /*
             This file contains a collection of sorting routines 
            */
              2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include "fatal.h"  5  6 typedef int ElementType;
  7  8void Swap(ElementType *Lhs, ElementType *Rhs)
  9{
 10    ElementType Tmp;
 11     Tmp = *Lhs;
 12     *Lhs = *Rhs;
 13     *Rhs = Tmp;
 14}
 15 16void PrintArray(ElementType A[], int N)
 17{
 18int i;
 19for(i = 0; i < N; ++i)
 20         printf("%d ", A[i]);
 21     printf("\n");
 22}
 23 24void InsertionSort(ElementType A[], int N)
 25{
 26int i, j;
 27    ElementType Tmp;
 28 29for(i = 1; i < N; ++i)
 30    {
 31         Tmp = A[i];
 32for(j = i; j >= 1 && A[j-1] > Tmp; --j)
 33             A[j] = A[j-1];
 34         A[j] = Tmp;
 35    }
 36}
 37 38void ShellSort(ElementType A[], int N)
 39{
 40int i, j, Increment;
 41    ElementType Tmp;
 42 43for(Increment = N/2; Increment > 0; Increment /=2)
 44    {
 45for(i = Increment; i < N; ++i)
 46        {
 47             Tmp = A[i];
 48for(j = i; j >= Increment && A[j-Increment] > Tmp; j -= Increment)
 49                 A[j] = A[j-Increment];
 50             A[j] = Tmp;
 51        }
 52    }
 53}
 54 55// 简单选择排序 56void SelectSort(ElementType A[], int N)
 57{
 58int i, j;
 59int MinIdx;
 60 61for(i = 0; i < N-1; ++i) // N-1次即可完成排序 62    {
 63         MinIdx = i;
 64for(j = i+1; j < N; ++j) // 在[i+1, N)范围内查找最小值 65        {
 66if(A[j] < A[MinIdx])
 67                 MinIdx = j;
 68        }
 69if(i != MinIdx)
 70             Swap(&A[i], &A[MinIdx]);
 71    }
 72}
 73 74// 简单选择排序的改进: 在查找最小值的同时，可以查找出最大值,
 75// 最小值和第一个元素交换，最大值和最后一个元素交换。 76void SelectSortII(ElementType A[], int N)
 77{
 78int i, j;
 79int MinIdx, MaxIdx;
 80 81for(i = 0; i < N/2; ++i) // 一次排好最小值和最大值, 因此N/2次循环可以排好整个序列 82    {
 83         MinIdx = i;
 84         MaxIdx = N-i-1;
 85for(j = i; j < N-i; ++j) // 在[i, N-i)范围内查找最小值和最大值, 注意不能从i+1开始 86        {
 87if(A[j] < A[MinIdx])
 88                 MinIdx = j;
 89if(A[j] > A[MaxIdx])
 90                 MaxIdx = j;
 91        }
 92 93if(MinIdx != i)
 94             Swap(&A[MinIdx], &A[i]);
 95if(MaxIdx != N-i-1)
 96             Swap(&A[MaxIdx], &A[N-i-1]);
 97    }
 98}
 99100// 第6.3节讲的二叉堆左儿子为2*i, 右儿子为2*i+1, 下标为0的元素用于标记
101// 堆排序中不使用头节点, 因此左儿子为2*i+1, 右儿子为2*i+2102#define LeftChild(i) ( 2 * (i) + 1 )
103104void PercDown(ElementType A[], int i, int N)
105{
106int Child;
107    ElementType Tmp;
108109for(Tmp = A[i]; LeftChild(i) < N; i = Child)
110    {
111         Child = LeftChild(i);
112if(Child != N-1 && A[Child + 1] > A[Child])
113             Child++;
114115if(Tmp < A[Child])
116             A[i] = A[Child];
117else118break;
119    }
120     A[i] = Tmp;
121}
122123void HeapSort(ElementType A[], int N)
124{
125int i;
126127for(i = N/2; i >= 0; --i) /* BuildHeap */128        PercDown(A, i, N);
129130for(i = N-1; i > 0; --i)  /* DeleteMax */131    {
132         Swap(&A[0], &A[i]);
133         PercDown(A, 0, i);
134    }
135}
136137// N个元素需要N-1趟才可以排好, i的取值为[0, N-1);
138// 每趟排序都会确定最后一个元素, 因此j的上界为N-i,
139// 考虑到循环内部使用了j+1, 因此上界应该为N-i-1,
140// 每趟比较从第0个元素开始, 下界为0141void BubbleSort(ElementType A[], int N)
142{
143int i, j;
144145for(i = 0; i < N-1; ++i)
146    {
147for(j = 0; j < N-i-1; ++j)
148        {
149if(A[j] > A[j+1])
150                 Swap(&A[j], &A[j+1]);
151        }
152         PrintArray(A, 7);
153    }
154}
155156/* Lpos = start of left half, Rpos = start of right half */157void Merge(ElementType A[], ElementType TmpArray[],
158int Lpos, int Rpos, int RightEnd)
159{
160int i, LeftEnd, NumElements, TmpPos;
161162     LeftEnd = Rpos - 1;
163     TmpPos = Lpos;
164     NumElements = RightEnd - Lpos + 1;
165166/* main loop */167while(Lpos <= LeftEnd && Rpos <= RightEnd)
168if(A[Lpos] < A[Rpos])
169             TmpArray[TmpPos++] = A[Lpos++];
170else171             TmpArray[TmpPos++] = A[Rpos++];
172while(Lpos <= LeftEnd)  /* Copy rest of first half */173         TmpArray[TmpPos++] = A[Lpos++];
174while(Rpos <= RightEnd) /* Copy rest of second half */175         TmpArray[TmpPos++] = A[Rpos++];
176177/* Copy TmpArray back */178for(i = 0; i < NumElements; ++i, RightEnd--)
179         A[RightEnd] = TmpArray[RightEnd];
180}
181182void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right)
183{
184int Center;
185186if(Left < Right)
187    {
188         Center = (Left + Right) / 2;
189        MSort(A, TmpArray, Left, Center);
190         MSort(A, TmpArray, Center+1, Right);
191         Merge(A, TmpArray, Left, Center+1, Right);
192    }
193}
194195// MergeSort为递归例程MSort的驱动程序196void MergeSort(ElementType A[], int N)
197{
198     ElementType *TmpArray;
199200     TmpArray = (ElementType *)malloc(N * sizeof(ElementType));
201if(TmpArray != NULL)
202    {
203         MSort(A, TmpArray, 0, N-1); // 注意是N-1204free(TmpArray);
205    }
206else207         FatalError("Out of space!");
208}
209210/* Return median of Left, Center, and Right */211/* Order these and hide the pivot */212 ElementType Median3(ElementType A[], int Left, int Right)
213{
214int Center = (Left + Right) / 2;
215216if(A[Left] > A[Center])
217         Swap(&A[Left], &A[Center]);
218if(A[Left] > A[Right])
219         Swap(&A[Left], &A[Right]);
220if(A[Center] > A[Right])
221         Swap(&A[Center], &A[Right]);
222223/* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */224225     Swap(&A[Center], &A[Right-1]); /* Hide pivot */226return A[Right-1];             /* Return pivot */227}
228229#define Cutoff (3)
230231void Qsort(ElementType A[], int Left, int Right)
232{
233int i, j;
234    ElementType Pivot;
235236if(Left + Cutoff <= Right)
237    {
238         Pivot = Median3(A, Left, Right);
239         i = Left;
240         j = Right - 1;
241for( ; ; )
242        {
243while(A[++i] < Pivot){}
244while(A[--j] > Pivot){}
245if(i < j)
246                 Swap(&A[i], &A[j]);
247else248break;
249        }
250         Swap(&A[i], &A[Right-1]); /* Restore pivot */251252         Qsort(A, Left, i - 1);
253         Qsort(A, i + 1, Right);
254    }
255else/* Do an insertion sort on the subarray */256         InsertionSort(A + Left, Right - Left + 1);
257}
258259/*260// 测试通过, 选取最后一个元素为枢纽元的排序方法
261void Qsort(ElementType A[], int Left, int Right)
262{
263    int i, j;
264    ElementType Pivot;
265266    if(Left < Right) // 这里用 < 或者 <=都可以
267    {
268        Pivot = A[Right]; // 选择最右边的元素为枢纽元
269        i = Left-1, j = Right; // 注意这里i= Left - 1  !!!!
270        for( ; ; )
271        {
272            while(A[++i] < Pivot){}
273            while(A[--j] > Pivot){}
274            if(i < j)
275                Swap(&A[i], &A[j]);
276            else
277                break;
278        }
279        Swap(&A[i], &A[Right]);
280281        Qsort(A, Left, i - 1);
282        Qsort(A, i + 1, Right);
283    }
284}
285*/286287void QuickSort(ElementType A[], int N)
288{
289     Qsort(A, 0, N-1);
290}
291292/* Places the kth smallest element in the kth position */293/* Because arrays start at 0, this will be index k-1 */294void Qselect(ElementType A[], int k, int Left, int Right)
295{
296int i, j;
297    ElementType Pivot;
298299if(Left + Cutoff <= Right)
300    {
301         Pivot = Median3(A, Left, Right);
302         i = Left;
303         j = Right - 1;
304for(; ;)
305        {
306while(A[++i] < Pivot){}
307while(A[--j] > Pivot){}
308if(i < j)
309                 Swap(&A[i], &A[j]);
310else311break;
312        }
313         Swap(&A[i], &A[Right-1]); /* Restore pivot */314315if(k <= i)
316             Qselect(A, k, Left, i - 1);
317else318             Qselect(A, k, i + 1, Right);
319    }
320else/* Do an insertion sort on the subarray */321         InsertionSort(A + Left, Right - Left + 1);
322}
323324/* ROUTINES TO TEST THE SORTS */325void Permute(ElementType A[], int N)
326{
327int i;
328329for(i = 0; i < N; ++i)
330         A[i] = i;
331for(i = 1; i < N; ++i)
332         Swap(&A[i], &A[rand() % (i + 1)]);
333}
334335void CheckSort(ElementType A[], int N)
336{
337int i;
338339for(i = 0; i < N; ++i)
340if(A[i] != i)
341             printf("Sort fails: %d\n", i);
342     printf("Check completed\n");
343}
344345void Copy(ElementType Lhs[], const ElementType Rhs[], int N)
346{
347int i;
348for(i = 0; i < N; ++i)
349         Lhs[i] = Rhs[i];
350}
351352#define MaxSize 7000
353int Arr1[MaxSize];
354int Arr2[MaxSize];
355356int main()
357{
358int i;
359for(i = 0; i < 10; ++i)
360    {
361         Permute(Arr2, MaxSize); // 生成一个随机数组362363        Copy(Arr1, Arr2, MaxSize);
364        InsertionSort(Arr1, MaxSize);
365        CheckSort(Arr1, MaxSize);
366367        Copy(Arr1, Arr2, MaxSize);
368        ShellSort(Arr1, MaxSize);
369        CheckSort(Arr1, MaxSize);
370371        Copy(Arr1, Arr2, MaxSize);
372        HeapSort(Arr1, MaxSize);
373        CheckSort(Arr1, MaxSize);
374375        Copy(Arr1, Arr2, MaxSize);
376        MergeSort(Arr1, MaxSize);
377        CheckSort(Arr1, MaxSize);
378379        Copy(Arr1, Arr2, MaxSize);
380        QuickSort(Arr1, MaxSize);
381        CheckSort(Arr1, MaxSize);
382383        Copy(Arr1, Arr2, MaxSize);
384         Qselect(Arr1, MaxSize / 2 + 1 + i, 0, MaxSize - 1);
385if(Arr1[MaxSize / 2 + 1 + i] != MaxSize / 2 + 1 + i)
386              printf("Select error: %d %d\n", MaxSize / 2 + 1 + i, Arr1[MaxSize / 2 + 1 + i]);
387else388              printf("Select works\n");
389    }
390return0;
391 }