排序算法汇总总结

1、排序算法汇总总结一、插入排序直接插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。代码实现：#include <stdio.h>#include <stdlib.h>void swap(int *p1, int *p2) int temp; temp=*p1; *p1=*p2; *p

2、2=temp;void insertSort(int *a,int len) int i,j; for(i=0;i<len;i+) for(j=i+1;j>=1;j-) if(aj<aj-1) swap(&aj,&aj-1); 希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。它的基本思想是先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<<

3、;d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。代码实现：#include <stdio.h>#include <stdlib.h>void swap(int *p1, int *p2) int temp; temp=*p1; *p1=*p2; *p2=temp;void shell(int *a,int d,int len) int i,j; for(i=d+1;i<len;i+) for(j=i+d;j>=i && j<len;j-) if(aj<aj-d) swap(&

4、;aj,&aj-d); void shellSort(int *a,int d,int len) while(d>=1) shell(a,d,len); d=d/2; 二、交换排序冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。代码实现：(swap函数同前 以后同)void bubbleSort(int *a,int len) int i,j,chan

5、ge; for(i=0;i<len;i+) change=0; for(j=len-1;j>i;j-) if(aj<aj-1) change=1; swap(&aj,&aj-1); if(!change) break; 快速排序是由东尼·霍尔所发展的一种排序算法 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。代码实现：int partition(int *a,int s,int e) i

6、nt roll=as,i,j; for(i=s+1,j=i;i<=e;i+) if(ai<roll) swap(&ai,&aj); j+; swap(&as,&aj-1); return j-1;void quickSort(int *a, int start,int end) if(start<=end) int split=partition(a,start,end); quickSort(a,start,split-1); quickSort(a,split+1,end); 三、选择排序直接选择排序(Selection sort)是一种简

7、单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾(目前已被排序的序列)。以此类推，直到所有元素均排序完毕。代码实现：void selectSort(int *a, int len) int i,j,min,mark; for(i=0;i<len;i+) min=ai; for(j=i+1;j<len;j+) if(aj<min) min=aj; mark=j if(min!=ai) swap(&ai,&amark); 堆排序（Heapsort）是指利用

8、堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点代码实现：void shift(int *a,int r,int len) int j,maxid; for(j=r;j<=len/2;) maxid=j; if(2*j<len && a2*j>aj) maxid=2*j; if(2*j+1<len && a2*j+1>amaxid) maxid=2*j+1; if(maxid!=j) swap(&amaxid,&aj); void

9、buildHeap(int *a, int len) /为便宜计算 a的下标从1开始 构建大顶堆 int i; for(i=len/2;i>0;i-) shift(a,i,len);void heapSort(int *a, int len) int clen; buildHeap(a,len); swap(&a1,&alen); for(clen=len-1;clen>0;clen-) shift(a,1,clen); swap(&a1,&aclen); 四、归并排序归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的

10、排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。算法描述归并操作的过程如下：1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置4. 重复步骤3直到某一指针达到序列尾5. 将另一序列剩下的所有元素直接复制到合并序列尾代码实现：void merge(int *a,int start,int mid,int end) if(start>mid | mid >end ) return

11、; int i=start,j=mid+1,k=0; int *L=(int *)malloc(end-start+1)*sizeof(int); while(i<=mid && j<=end) if(ai<aj) Lk+=ai+; else Lk+=aj+; while(i<=mid) Lk+=ai+; while(j<=end) Lk+=aj+; for(i=start,j=0;i<=end;i+,j+) ai=Lj; free(L);void mergeSort(int *a, int start,int end) if(start&l

12、t;end) int mid=(start+end)/2; mergeSort(a,start,mid); mergeSort(a,mid+1,end); merge(a,start,mid,end); 五、基数排序基数排序(Radix sort)是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。算法实现（未验证正确性）：struct DNode int data; DNode *next;struct Table int id; DNode *fisrt;i

13、nt digit(int num,int loc) for(int i=1;i<loc;i+) num/=10; int res=num%10; return res;int maxCount(int *a,int len) int max=0,n,num; for(int i=0;i<len;i+) n=0; num=ai; while(num) num/=10; n+; if(n>max) max=n; return max;void radixSort(int *a,int len) int maxloc=maxcount(a,len); DNode *ptemp; T

14、able *t=(Table *)malloc(10 * sizeof(Table); for(int i=0;i<10;i+) ti->id=i; ti->first=NULL; for(int j=1;j<maxcount;j+) for(int k=0;k<len;k+) int idm=digit(ak,j); DNode *p=tidm->first; while(pt->next!=NULL) p=p->next; DNode *d=(DNode *)malloc(sizeof(DNode); d->data=ak; d->

15、;next=p->next; p->next=d; for(int i=0,k=0;i<=9;i+) while(ti->first!=NULL) ak-=ti->first->data; ptemp=ti->first; ti->first=ti->first->next; free(ptemp); 六、排序算法特点，算法复杂度和比较直接插入排序如果目标是把n个元素的序列升序排列，那么采用直接插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降

16、序排列，那么此时需要进行的比较共有n(n-1)/2次。直接插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说直接插入排序算法复杂度为O(n2)。因而，直接插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么直接插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。希尔排序希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)

17、， 没有快速排序算法快 O(N*(logN)，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法.希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。

18、所以，希尔排序的时间复杂度会比o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的冒泡排序时间复杂度为O（n2），虽然不及堆排序、快速排序的O（nlogn，底数为2），但是有两个优点：1.“编程复杂度”很低，很容易写出代码；2.具有稳定性。其中若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行

19、n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。快速排序 在最好的情况，每次我们执行一次分割，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递回调用处理一半大小的数列。因此，在到达大小为一的数列前，我们只要作 log n 次巢状的调用。这个意思就是调用树的深度是O(log n)。但是在同一阶层的两个程序调用中，不会处理到原来数列的相同部份；因此，程序调用的每一阶层总共全部仅需要O(n)的时间（每个调用有某些共同的额外耗费，但是因为在每一阶层仅仅只有O(n)个调用，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。另外一个方法是为

20、T(n)设立一个递回关系式，也就是需要排序大小为n的数列所需要的时间。在最好的情况下，因为一个单独的快速排序调用牵涉了O(n)的工作，加上对n/2大小之数列的两个递回调用，这个关系式可以是：T(n) = O(n) + 2T(n/2)解决这种关系式型态的标准数学归纳法技巧告诉我们T(n) = O(n log n)。事实上，并不需要把数列如此精确地分割；即使如果每个基准值将元素分开为 99% 在一边和 1% 在另一边，调用的深度仍然限制在 100log n，所以全部执行时间依然是O(n log n)。然而，在最坏的情况是，两子数列拥有大各为 1 和 n-1，且调用树（call tree）变成为一个

21、 n 个巢状（nested）呼叫的线性连串（chain）。第 i 次呼叫作了O(n-i)的工作量，且递回关系式为：T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)这与插入排序和选择排序有相同的关系式，以及它被解为T(n) = O(n2)。讨论平均复杂度情况下，即使如果我们无法随机地选择基准数值，对于它的输入之所有可能排列，快速排序仍然只需要O(n log n)时间。因为这个平均是简单地将输入之所有可能排列的时间加总起来，除以n这个因子，相当于从输入之中选择一个随机的排列。当我们这样作，基准值本质上就是随机的，导致这个算法与乱数快速排序有一样的执行时

22、间。更精确地说，对于输入顺序之所有排列情形的平均比较次数，可以借由解出这个递回关系式可以精确地算出来。在这里，n-1 是分割所使用的比较次数。因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分割的平均。这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。这意味着，它比最坏情况较接近最好情况。这个快速的平均执行时间，是快速排序比其他排序算法有实际的优势之另一个原因。讨论空间复杂度时 被快速排序所使用的空间，依照使用的版本而定。使用原地（in-place）分割的快速排序版本，在任何递回呼叫前，仅会使用固定的額外空間。然而，如果需要产生O(log

23、n)巢状递回呼叫，它需要在他们每一个储存一个固定数量的资讯。因为最好的情况最多需要O(log n)次的巢状递回呼叫，所以它需要O(log n)的空间。最坏情况下需要O(n)次巢状递回呼叫，因此需要O(n)的空间。然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列，我们必须要记住我们的变量像是left和right，不再被认为是占据固定的空间；也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量，实际上快速排序在最好跟平均的情况下，需要O(log2 n)空间的位元数，以及最坏情况下O(n log n)的空间。然而，这并不会太可怕，因为如果一个数列

24、大部份都是不同的元素，那么数列本身也会占据O(n log n)的空间字节。非原地版本的快速排序，在它的任何递回呼叫前需要使用O(n)空间。在最好的情况下，它的空间仍然限制在O(n)，因为递回的每一阶中，使用与上一次所使用最多空间的一半，且它的最坏情况是很恐怖的，需要空间，远比数列本身还多。如果这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，如果数列元素的大部份都是不同的，每一个将会需要大约O(log n)为原来储存，导致最好情况是O(n log n)和最坏情况是O(n2 log n)的空间需求。直接选择排序选择排序的交换操作介于0和(n-1)次之间。选择排序的比较操作为n(n

25、-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。比较次数O(n2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+.+1=n*(n-1)/2。 交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。堆排序堆排序的平均时间复杂度为(nlogn)，空间复杂度为(1)。由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做

26、两个步骤：是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。 归并排序归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。基数排序基数排序的时间复杂度是 O(k·n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n)，因为k的大小一般会受到 n 的影响。 以排序n个不同整数来举例，假定这些整数以B为底，这样

27、每位数都有B个不同的数字，k就一定不小于logB(n)。由于有B个不同的数字，所以就需要B个不同的桶，在每一轮比较的时候都需要平均n·log2(B) 次比较来把整数放到合适的桶中去，所以就有：· k 大于或等于 logB(n)· 每一轮(平均)需要 n·log2(B) 次比较所以，基数排序的平均时间T就是：T logB(n)·n·log2(B) = log2(n)·logB(2)·n·log2(B) = log2(n)·n·logB(2)·log2(B) = n·l

28、og2(n)所以和比较排序相似，基数排序需要的比较次数：T n·log2(n)。 故其时间复杂度为 (n·log2(n) = (n·log n) 。七、不同条件下，排序方法的选择(1)若n较小(如n50)，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。 (2)若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归