首页 > 代码库 > C语言排序算法复习
C语言排序算法复习
排序算法有很多种，这里在复习和分析的基础上，做一个自己的总结；
首先要知道有哪些排序算法，google一下，有云C语言7大经典排序算法（也有8大）。主要包括冒泡排序，快速排序，选择排序，插入排序，希尔排序，归并排序，堆排序，8大的还有基数排序。各有各的版本，代码写法也各不相同。所以这里以整理思路为先，代码只是作为自己的一个备份。
搞清楚的概念：稳定排序和不稳定排序，就看序列中两个值相等的数，排完序之后的相对位置是否改变，如果改变了就不稳定。
内部排序和外部排序，只用到内存即可完成排序的就叫内部排序，外部排序因为序列比较长，用到了外部存储。
算法好坏标准：时间复杂度和空间复杂度。分析T(n)=O(f(n))为主，这个还是比较简单的理解一下就行，因为这种方法本身也是一种统计估计。
针对3中存储结构，1、以一组连续的地址单元作为存储结构；2、以链表作为存储结构；3、和1一样存储，但是通过建立辅助表来进行排序。
插入类排序：直接插入排序，希尔排序；
第一个算法，直接插入算法，很简单，假如我们的数组是R[n+1]，第一个作为交换时用的中间变量；那么R[1]作为最初的有序区，从i=2开始不断插入R[i]，插入时跟有序区中的R[j]进行比较；R[0]在while循环中可以作为监视哨，以防下标变量j越界，避免了while循环检测j是否越界，测试循环条件的时间可以减少一半。
算法的时间复杂度为O(n2)；排序中最坏情况就是全逆序，最好情况，全正序；根据这样的两种情况来判断。
希尔排序，多了一个增量数组，有选择规则（使得增量值没有除1之外的公因子）如5.3.1；按照增量的值进行多轮排序，使得序列趋于正序列和交换次数较少的序列；希尔排序其实就是插入排序的改进版本。
算法复杂度O（nlgn）
交换类排序：冒泡排序和快速排序
冒泡排序，想法很简单，相邻两个元素比较，大的放后面，一趟一趟比，最后完成排序。快速排序就是对这一过程进行了优化；还有双向冒泡法，改进算法，这里不深入了。冒泡排序算法复杂度O(n2)
快速排序，这里首先要选取一个基准，一般都是一上来就吧R[0]作为基准，大的放在右边，小的放在左边，形成两个子序列，然后R[0]在中间，对两个子序列继续重复上一过程，直到序列里面的个数为1；从而可以看出，这个算法可以用递归。 算法复杂度O(n2)；但是他是目前基于比较的内部排序方法中平均性能最好的。但是快读排序不稳定。
选择类排序：直接选择排序，和直接插入排序作比较，其实差不多，不过这里是选择最小的一个作为有序列的R[1]，进行n-1趟排序。也是不稳定的，算法复杂度O(n2)
归并排序：顾名思义，是合并，将一些较小的有序的序列进行合并从而成为整个有序序列。他是稳定的排序，复杂度为O(nlgn)，一般应用时先采用直接插入排序得到几个有序序列，然后再进行归并，这样仍然是稳定的。
完了之后就是要把思路转化为程序。毕竟写出程序的能力才是最终要有的。
#include <stdio.h>#include <stdlib.h>#define n 8typedef struct{ int key;}rectype;rectype R[n+1];void insertsort(rectype R[]){ int i,j; for(i=2;i<=n;i++) { if(R[i].key<R[i-1].key) { R[0]=R[i]; j=i-1; while(R[0].key<R[j].key) { R[j+1]=R[j--];//jiang guanjianzi dayu R[i].key de jilu houyi } R[j+1]=R[0]; } }}void shellsort(rectype R[],int d[],int t){ int i,j,k; for(k=0;k<t;k++) for(i=d[k]+1;i<=n;i++) if(R[i].key<R[i-d[k]].key) { R[0]=R[i]; j=i-d[k]; while(j>0&&R[0].key<R[j].key) { R[j+d[k]]=R[i]; j=j-d[k]; R[j-d[k]]=R[0]; } }}void bubblesort(rectype R[]){ int i,j,swap; for(i=1;i<n;i++) { swap=0; for(j=n;j>i;j--) if(R[j-1].key>R[j].key) { R[0]=R[j-1]; R[j-1]=R[j]; R[j]=R[0]; swap=1; } if(!swap) break; }}int partition(rectype R[],int low,int high){ rectype pivot=R[low]; while(low<high) { while(low<high&&R[high].key>=pivot.key) high--; if(low<high) R[low++]=R[high]; while(low<high&&R[low].key<=pivot.key) low++; if(low<high) R[high--]=R[low]; } R[low]=pivot; return low;}void quicksort(rectype R[],int s,int t){ int i; if(s<t) { i=partition(R,s,t); quicksort(R,s,i-1); quicksort(R,i+1,t); }}void selectsort(rectype R[],int m){ int i,j,k; rectype temp; for(i=1;i<m;i++) { k=i; for(j=i+1;j<=m;j++) if(R[j].key<R[k].key) k=j; if(k!=i) { temp=R[i]; R[i]=R[k]; R[k]=temp; } }}void merge(rectype R[],int low,int mid,int high){ int i,j,k; i=low;j=mid+1;k=0; rectype *R1=(rectype*)malloc((high-low+1)*sizeof(rectype)); if(!R1){printf("failed");exit(0);} while((i<=mid)&&(j<=high)) { if(R[i].key<=R[j].key) R1[k++]=R[i++]; else R1[k++]=R[j++]; } while(i<=mid) R1[k++]=R[i++]; while(j<=high) R1[k++]=R[j++]; for(k=0,i=low;i<high;k++,i++) R[i]=R1[k];}void mergepass(rectype R[],int length){ int i=1; while(i+2*length-1<=n) { merge(R,i,i+length-1,i+2*length-1); i=i+2*length; } if((i+length-1)<n) { merge(R,i,i+length-1,n-1); }}void mergesort(rectype R[]){ int length; for(length=1;length<n;length*=2) mergepass(R,length);}int main(){ int i; int d[]={5,3,1}; rectype R[]={{0},{12},{16},{23},{58},{68},{2},{7},{9}}; insertsort(R); for(i=1;i<=n;i++) printf("%d ",R[i].key); printf("\n"); shellsort(R,d,2); for(i=1;i<=n;i++) printf("%d ",R[i].key); printf("\n"); bubblesort(R); for(i=1;i<=n;i++) printf("%d ",R[i].key); printf("\n"); quicksort(R,1,8); for(i=1;i<=n;i++) printf("%d ",R[i].key); printf("\n"); selectsort(R,8); for(i=1;i<=n;i++) printf("%d ",R[i].key); printf("\n"); mergesort(R); for(i=1;i<=n;i++) printf("%d ",R[i].key); printf("\n"); }