六种排序算法总结
今天花了点时间看《数据结构与算法分析（C语言描述）》，把里面涉及到的几种排序算法大致总结了一下。不过这书里面的一些排序示例存在明显错误，所以在看的时候需要注意一下。
1、快速排序。号称实践中最快的已知排序算法。平均运行时间为O(N log N)，最坏情形的性能为O(N^2)。
快速排序算法思路：
1、选择枢纽元。
2、初始化i为Left+1，j为Right-2。i向右移，如果A[i]均小于枢纽元，则继续右移。j向左移，如果A[j]均小于枢纽元，则继续向左移。
3、如果此时i仍在j左边，则交换A[i]和A[j]（因为此时A[i]大于枢纽元，而A[j]小于枢纽元，则交换之后小的元素在左大的元素在右）,直至i>j时此趟排序结束。
4、交换A[i]和枢纽元的位置。此时A[i]的左边均是小于A[i]的，而右边则均大于A[i]。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
/** * 快速排序 **/ #define Cutoff 3 /* 选枢纽元，先从小到大排列A[Left], A[Center], A[Right]，A[Center]为枢纽元，并将A[Center]与A[Right-1]进行交换。 因为A[Left]比枢纽元小，所以作为A[j]的警戒标志，不必担心j越界。由于i将停在那些等于枢纽元的关键字处，故将枢纽元放置在Right-1的位置，提供i的警戒标志。*/ int Median3(int A[], int Left, int Right) { int Center = (Left + Right) / 2; if (A[Left] > A[Center]) swap(A[Left], A[Center]); if (A[Left] > A[Right]) swap(A[Left], A[Right]); if (A[Center] > A[Right]) swap(A[Center], A[Right]); swap(A[Center], A[Right-1]); return A[Right - 1]; } //快速排序 void Qsort(int A[], int Left, int Right) { int i,j; int Pivot; //枢纽元 if(Left + Cutoff <= Right) { Pivot = Median3(A, Left, Right); i = Left; j = Right - 1; for(; ;) //每次交换之后继续执行循环 { while(A[++i] < Pivot){} while(A[--j] > Pivot){} if(i < j) swap(A[i], A[j]); else break; } swap(A[i], A[Right-1]); Qsort(A, Left, i-1); //分治法继续快速排序A[i]元素左右两边的数 Qsort(A, i+1, Right); } else InsertionSort(A+Left, Right-Left+1); //A+Left： A[Left]开始长为Right-Left+1的数组 } |
2、插入排序，时间复杂度为O(N^2)。
插入排序算法思路：
1、将数组的第一个元素当作已经排序的初始数组，而后面的元素通过逐一与前一个元素比较大小，插入到初始数组的适当位置中。
2、若前一个元素较大，则与后一个元素交换（即插入到前一个元素的前面），继续比较；若后一个元素较大，则此趟排序结束。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void InsertionSort(int A[], int N) { int j,p; int Tmp; for(p=1; p<N; p++) { Tmp = A[p]; for(j=p; j>0 && A[j-1]>Tmp; j--) { A[j] = A[j-1]; } A[j] = Tmp; } } |
3、堆排序，时间复杂度为O(N log N)。
堆排序算法思路：此处为最大堆排序。
1、建立二叉树。从倒数第一个父亲结点开始，每次比较父亲结点和其儿子结点的大小，大的结点交换到父亲结点的位置。从而建立起一个堆。在父亲结点发生变化时，需重新与其儿子结点进行排序。
2、将位于根结点的元素与堆的最后一个元素进行交换，将堆的大小缩减1，继续递归地进行堆排序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#define LeftChild(i) (2 * (i) + 1) //BuildHeap void PercDown(int A[], int i, int N) { int Child; int Tmp; for(Tmp=A[i]; LeftChild(i)<N; i=Child) //在子树父亲结点变化时，重新将子树进行排列。 { Child = LeftChild(i); if(Child!=N-1 && A[Child+1]>A[Child]) Child++; if(Tmp < A[Child]) A[i] = A[Child]; else break; } A[i] = Tmp; //此处的i已经为替换的元素的下标，即父亲结点与大的儿子结点进行互换,i=Child } //DeleteMax void Heapsort(int A[], int N) { int i; for(i=N/2; i>=0; i--) PercDown(A, i, N); for(i=N-1; i>0; i--) { swap(A[0], A[i]); //将最大元素和最后一个元素位置交换，堆缩小了1，继续进行堆排序 PercDown(A, 0, i); } } |
4、希尔排序（缩小增量排序），希尔排序的运行时间依赖于增量序列的选择。
希尔排序算法思路：使用希尔增量的希尔排序。
1、设置增量，示例中为 “/2″。
2、从A[Increment]开始，后面的元素逐一与前面隔Increment-1个位置的元素进行比较，若后面元素比前面元素小，则交换元素位置，若两个元素顺序不需改变，则继续向右执行比较。若递减Increment的元素存在的话则继续向前比较，直至元素大小顺序正确或元素不存在为止。
3、反复直到增量的值开始小于0则结束。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void Shellsort(int A[], int N) { int i,j,Increment; int Tmp; for(Increment=N/2; Increment>0; Increment/=2) { for(i=Increment; i<N; i++) { Tmp = A[i]; for(j=i; j>=Increment; j-=Increment) { if(Tmp<A[j-Increment]) A[j] = A[j - Increment]; else break; } A[j] = Tmp; //j=j-Increment } } } |
5、归并排序，运行时间为O(N log N)，不过很难用于主存排序，因为合并两个排序的表需要线性附加内存，算法中还要花费时间拷贝到临时数组等一些附加工作，严重放慢排序速度。
归并排序算法思路：
1、递归地将数组的前半部分和后半部分进行排序。
2、取两个输入数组A和B，一个输出数组C，以及三个计数器Aptr，Bptr，Cptr，它们初始置于对应数组的开始端。A[Aptr]和B[Bptr]中的最小者被拷贝到C中的下一个位置，相关计数器向前推进一步。当两个输入表有一个用完时，将另一个表中剩余部分拷贝到C中。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
void Merge(int A[], int TmpArray[], int Lpos, int Rpos, int RightEnd) { int i,LeftEnd,NumElements,TmpPos; LeftEnd = Rpos - 1; //Center-1 TmpPos = Lpos; NumElements = RightEnd - Lpos +1; while(Lpos <= LeftEnd && Rpos <= RightEnd) { if(A[Lpos] <= A[Rpos]) TmpArray[TmpPos++] = A[Lpos++]; else TmpArray[TmpPos++] = A[Rpos++]; } while(Lpos <= LeftEnd) //将有剩余元素的数组的尾部拷贝到临时数组尾部 TmpArray[TmpPos++] = A[Lpos++]; while(Rpos <= RightEnd) TmpArray[TmpPos++] = A[Rpos++]; for(i=0; i<NumElements; i++,RightEnd--) //将数组重新Copy到A中 A[RightEnd] = TmpArray[RightEnd]; } void MSort(int A[], int TmpArray[], int Left, int Right) { int Center; if(Left < Right) { Center = (Left + Right)/2; MSort(A, TmpArray, Left, Center); //递归地将数组分成前后两部分并排序 MSort(A, TmpArray, Center+1, Right); Merge(A, TmpArray, Left, Center+1, Right); } } void Mergesort(int A[], int N) { int *TmpArray; TmpArray = (int *)malloc(N * sizeof(int)); if(TmpArray != NULL) { MSort(A, TmpArray, 0, N-1); free(TmpArray); } else cout<<endl<<"No space for tmp array!"<<endl; } |
6、选择排序（最简单的排序）。
选择排序算法思路：首先找到最小元素，将其放在A[0]中，然后找到剩下的N-1个元素中的最小元素，将其存放在A[1]中，重复此过程直至找到第二大的元素，并将其存在A[N-1]中。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void Selectionsort(int A[], int N) { int i,j,k; for(i=0; i<N; i++) { k = i; for(j=i+1; j<N; j++) { if(A[j] < A[k]) k = j; } if(k != i) swap(A[i], A[k]); //依次选择最小的元素并交换到A[0],A[1],A[2]……中，依此类推。 } } |
以上为C++代码，如若需运行，必须包含algorithm的头文件（里面包含swap函数）。
