****************************************************************************************************
//直接插入排序,算法简洁，容易实现，时间复杂度O(N2),但较稳定，在基本有序和SIZE很小//时是最好的排序方法#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10001
main(){ int num[SIZE],i,j; clock_t start,end; start=clock(); randomize(); for(i=1;i<SIZE;i++) { num[i]=rand(); } for(i=2;i<SIZE;i++) { if(num[i]<num[i-1]) { num[0]=num[i]; num[i]=num[i-1]; for(j=i-2;num[0]<num[j+1];--j) num[j+1]=num[j]; num[j+1]=num[0]; } } end=clock(); for(i=1;i<SIZE;i++) printf("%d/n",num[i]); printf("time:%.20f",(end-start)/CLK_TCK); getch();}
****************************************************************************************************
//简单选择排序，属于选择排序，时间复杂度为O(N2)#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10001
main(){ int num[SIZE],i,j,seat,temp; clock_t start,end; start=clock(); randomize(); for(i=1;i<SIZE;i++) num[i]=rand(); for(i=SIZE-1;i>=1;i--) { seat=0; num[seat]=0; for(j=1;j<=i;j++) if(num[j]>num[seat]) seat=j; j--; temp=num[j]; num[j]=num[seat]; num[seat]=temp; } end=clock(); for(i=1;i<SIZE;i++) printf("%d/n",num[i]); printf("time:%.20f",(end-start)/CLK_TCK); getch();}
****************************************************************************************************
//希尔排序,属于插入排序，时间性能比较好，但不稳定#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10001
ShellInsert(int num[SIZE],int dk){ int i,j; for(i=dk+1;i<=SIZE;++i) if (num[i]>num[i-dk]) { num[0]=num[i]; num[i]=num[i-dk]; for(j=i-dk;j>0&&num[0]>num[j];j-=dk) num[j+dk]=num[j]; num[j+dk]=num[0]; }}
main(){ int num[SIZE],i,j,dk=100; clock_t start,end; start=clock(); randomize(); for(i=1;i<SIZE;i++) num[i]=rand()000; for(i=dk;i>=1;i--) ShellInsert(num,i); end=clock(); for(i=1;i<SIZE;i++) printf("%d/n",num[i]); printf("time:%.20f",(end-start)/CLK_TCK); getch();}
****************************************************************************************************
//快速排序,属于借助交换进行排序的方法，就平均时间而言，是最好的内部排序方法，时间//复杂度为O(N*LOG(N)),但若数列基本有序时，时间复杂度退化为O(N2),#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10001
partition(int num[SIZE],int low,int high){ num[0]=num[low]; while(low<high) { while(low<high&&num[high]>num[0]) --high; num[low]=num[high]; while(low<high&&num[low]<=num[0]) ++low; num[high]=num[low]; } num[low]=num[0]; return low;}
void Qsort(int num[SIZE],int low,int high){ int pivotloc; if(low<high) { pivotloc=partition(num,low,high); Qsort(num,low,pivotloc-1); Qsort(num,pivotloc+1,high); }}
main(){ int num[SIZE],i,j; clock_t start,end; start=clock(); randomize(); for(i=1;i<SIZE;i++) num[i]=rand()00; Qsort(num,1,SIZE-1); end=clock(); for(i=1;i<SIZE;i++) printf("%d/n",num[i]); printf("time:%.20f",(end-start)/ CLK_TCK); getch();}
****************************************************************************************************
//归并排序，时间复杂度为N(N*log(N)),最差情况也是，较为稳定，但实用性很差，较之堆排序//在N较大时，所用时间较省，但辅助存储量较多#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10001
Merge(int sr[SIZE],int tr[SIZE],int i,int m,int n){ int j,k; for(j=m+1,k=i;i<=m&&j<=n;++k) { if(sr[i]>sr[j]) tr[k]=sr[i++]; else tr[k]=sr[j++]; } if(i<=m) for(;i<=m;i++,k++) tr[k]=sr[i]; if(j<=n) for(;j<=n;j++,k++) tr[k]=sr[j];}
MSort(int sr[SIZE],int tr1[SIZE],int s,int t){ int tr2[SIZE],m; if(s==t) tr1[s]=sr[s]; else { m=(s+t)/2; MSort(sr,tr2,s,m); MSort(sr,tr2,m+1,t); Merge(tr2,tr1,s,m,t); }}
main(){ int num1[SIZE],num2[SIZE],i; clock_t start,end; start=clock(); randomize(); for(i=1;i<SIZE;i++) num1[i]=rand(); MSort(num1,num2,1,SIZE); end=clock(); for(i=1;i<SIZE;i++) printf("%d/n",num2[i]); printf("time:%.20f",(end-start)/CLK_TCK); getch();}
****************************************************************************************************
//堆排序，属于选择排序，时间复杂度为O(n*log(n)),最坏情况也是，但该方法对记录数较少//的文件不值得提倡#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10001
HeapAdjust(int num[SIZE],int s,int m){ int rc,j; rc=num[s]; for(j=2*s;j<=m;j*=2) { if(j<m&&num[j]>num[j+1]) ++j; if(rc<=num[j]) break; num[s]=num[j]; s=j; } num[s]=rc;}
main(){ int num[SIZE],i,j,temp; clock_t start,end; start=clock(); randomize(); for(i=1;i<SIZE-1;i++) num[i]=rand()00; for(i=SIZE/2;i>0;--i) HeapAdjust(num,i,SIZE-1); for(i=SIZE-1;i>1;--i) { temp=num[1]; num[1]=num[i]; num[i]=temp; HeapAdjust(num,1,i-1); } end=clock(); for(i=1;i<SIZE;i++) printf("%d/n",num[i]); printf("%.20f",(end-start)/CLK_TCK); getch();}
****************************************************************************************************
//冒泡排序，属于借助交换进行排序的方法，时间复杂度为O(N2)#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10001
main(){ int num[SIZE],i,j,temp; clock_t start,end; start=clock(); randomize(); for(i=1;i<SIZE;i++) num[i]=rand()00; for(i=SIZE-1;i>=2;i--) for(j=1;j<i;j++) if(num[j]>num[j+1]) { temp=num[j]; num[j]=num[j+1]; num[j+1]=temp; } end=clock(); for(i=1;i<SIZE;i++) printf("%d/n",num[i]); printf("time:%.20f",(end-start)/CLK_TCK); getch();}
****************************************************************************************************
//折半插入排序，属于简单排序，较之直接插入排序减少了关键字比较的次数，而移动的次数不变#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10001
main(){ int num[SIZE],i,j,low,mid,high; clock_t start,end; start=clock(); randomize(); for(i=1;i<SIZE;i++) num[i]=rand()000; for(i=2;i<SIZE;++i) { num[0]=num[i]; low=1; high=i-1; while(low<high) { mid=(low+high)/2; if(num[0]<num[mid]) high=mid-1; else low=mid+1; } for(j=i-1;j>=high+1;--j) num[j+1]=num[j]; num[high+1]=num[0]; } end=clock(); for(i=1;i<SIZE;i++) printf("%d/n",num[i]); printf("time:%.20f",(end-start)/CLK_TCK); getch();}
****************************************************************************************************
//二路插入排序，属于简单排序，较之折半插入排序又减少了记录的移动次数，约为POW(N,2)/8//但缺点是要付出多一倍的储存空间，并且当num[1]的元素为最小或最大，就完全失去优越性#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10000
main(){ int num[SIZE],temp[SIZE],index,i,first=1,final=1,mid; clock_t start,end; start=clock(); randomize(); for(i=0;i<SIZE;i++) num[i]=rand()0; temp[final]=num[0]; printf("/n"); for(i=1;i<SIZE;i++) { if(num[i]>=temp[final]) temp[++final]=num[i]; else if(num[i]<=temp[first]) { first=(first-1+SIZE)%SIZE; temp[first]=num[i]; } else { for(index=(final-1+SIZE)%SIZE;;index=(index-1+SIZE)%SIZE) { if(temp[index]<=num[i]) { mid=final++; while(mid!=index) { temp[(mid+1)%SIZE]=temp[mid]; mid=(mid-1+SIZE)%SIZE; } temp[(index+1)%SIZE]=num[i]; break; } } } } for(i=0;i<SIZE;++i) { num[i]=temp[first]; first=(first+1)%SIZE; } end=clock(); for(i=0;i<SIZE;i++) printf("%d/n",num[i]); printf("/ntime:%.20f",(end-start)/CLK_TCK); getch();}
****************************************************************************************************
以下两种方法都用于记录所占空间较大时，因为他们都采取了以修改指针来代替移动记录
****************************************************************************************************
//表插入排序，属插入排序，该方法的时间复杂度为O(N2)#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define SIZE 10001
void TableSort(int num[SIZE],int temp[SIZE]){ int i,j,indexpr,index; temp[0]=1; temp[1]=0; num[0]=num[1]; for(i=2;i<SIZE;i++) { if(num[i]>=num[0]) { for(index=temp[0];index!=0;indexpr=index,index=temp[index]); temp[indexpr]=i; temp[i]=0; num[0]=num[i]; } else if(num[i]<=num[temp[0]]) { temp[i]=temp[0]; temp[0]=i; } else { for(index=temp[0];index!=0;index=temp[index]) { if (num[index]>num[i]) { temp[i]=index; temp[indexpr]=i; break; } indexpr=index; } } }}
void Arrange(int num[SIZE],int temp[SIZE]){ int index,q,t,i; index=temp[0]; for(i=1;i<SIZE;i++) { while(index<i) index=temp[index]; q=temp[index]; if(index!=i) { t=num[i]; num[i]=num[index]; num[index]=t; temp[index]=temp[i]; temp[i]=index; } index=q; }}
main(){ int num[SIZE],temp[SIZE],i; clock_t start,end; start=clock(); randomize(); for(i=1;i<SIZE;i++) num[i]=rand()0; TableSort(num,temp); Arrange(num,temp); end=clock(); for(i=0;i<SIZE;i++) printf("%d/n",num[i]); printf("/ntime:%.20f",(end-start)/CLK_TCK); getch();}
****************************************************************************************************
//基数排序，是一种与前面所有排序都不同的排序方法，该方法不需要进行关键字间的比较//它是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法，其时间复杂度为O(d*n)//它最适合N值很大而关键字较小的序列，若关键字也很大，而序列中大多数记录的最高位关//键字均不同，则亦可先按最高位关键字不同将需类分成若干小的子序列，而后进行直接插入排序#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "time.h"#define MAX_NUM_OF_KEY 1#define RADIX 10#define SIZE 11
typedef struct{ int keys[MAX_NUM_OF_KEY]; int next;}Node;
Distribute(Node array[SIZE],int i,int f[RADIX],int e[RADIX]){ int j,p,key; for(j=0;j<RADIX;j++) f[j]=0; for(p=array[0].next;p;p=array[p].next) { key=array[p].keys[i]; if(!f[key]) f[key]=p; else array[e[key]].next=p; e[key]=p; }}
Collect(Node array[SIZE],int i,int f[RADIX],int e[RADIX]){ int j,t; for(j=0;!f[j];j++); array[0].next=f[j]; t=e[j]; while(j<RADIX) { for(j++;j<RADIX-1&&!f[j];j++); if(f[j]) { array[t].next=f[j]; t=e[j]; } } array[t].next=0;}
main(){ Node array[SIZE]; int f[RADIX],e[RADIX],i; clock_t start,end; start=clock(); randomize(); for(i=0;i<SIZE-1;i++) { array[i+1].keys[0]=rand(); array[i].next=i+1; } array[SIZE-1].next=0; for(i=0;i<MAX_NUM_OF_KEY;i++) { Distribute(array,i,f,e); Collect(array,i,f,e); } end=clock(); for(i=array[0].next;i;i=array[i].next) printf("%d/n",array[i].keys[0]); printf("time:%.20f",(end-start)/CLK_TCK); getch();}
