C语言的四种排序
简单选择排序
/*对整型数组的元素进行简单选择排序(源程序的整型简单选择排序)*/ #include
#include
#define N 6
void taxis(int b[],int k)
{
int i,j,temp;
for(i=0;i for(j=i+1;j if(b[i]>b[j]) { temp=b[i]; b[i]=b[j]; b[j]=temp; } } void main() { int a[N]={9,8,5,6,2,0},i; clrscr(); taxis(a,N); for(i=0;i { printf("%d",a[i]); if(i printf(","); } } /*对整型数组的元素进行简单选择排序(源程序的整型排序-指针))*/ #include #include #define N 6 void taxis(int *p1,int k) { int temp,*p2,*p3; for(p2=p1;p2 for(p3=p2+1;p3 if(*p2>*p3) { temp=*p2; *p2=*p3; *p3=temp; } } void main() { int a[N]={9,8,5,6,2,0},*p; clrscr(); taxis(a,N); for(p=a;p printf("%d",*p); if(p printf(","); } } /*将字符串按其的长度(字母对应的ASCⅡ值由小到大)进行简单选择排序(源程序的字符串长度排序)*/ #include #include #include #define N 5 void taxis(char *p1[],int k) { int i,j; char *temp; for(i=0;i for(j=i+1;j if(strlen(p1[i])>strlen(p1[j])) { temp=p1[i]; p1[i]=p1[j]; p1[j]=temp; } } void main() { char *a[]={"Follow","BASIC","Great","FORTRAN","Computer"}; int i; clrscr(); taxis(a,N); printf("The result of taxis is:\n"); for(i=0;i printf("%s\n",a[i]); } /*将字符串按字母顺序(字母对应的ASCⅡ值由小到大)进行简单选择排序(源程序的字符串顺序排序)*/ #include #include #include #define N 5 void taxis(char *p1[],int k) { int i,j; char *temp; for(i=0;i for(j=i+1;j if(strcmp(p1[i],p1[j])>0) { temp=p1[i]; p1[i]=p1[j]; p1[j]=temp; } } { char *a[]={"Follow","BASIC","Great","FORTRAN","Computer"}; int i; clrscr(); taxis(a,N); for(i=0;i printf("%s\n",a[i]); } /*将整型数组的元素进行简单选择排序(终端输入的整型排序),如果连续出现3个为0的数据,*/ /*则默认判断这3个为0的数据无效以和其后面是没有数据,*/ /*即不输出这3个为0的数据以和其后面的数据(元素来自终端)*/ #include #include #define N 50 void taxis(int b[],int k) { int i,j,temp; for(i=0;i for(j=i+1;j if(b[i]>b[j]) { if(b[j]==0&&b[j+1]==0&&b[j+2]==0) break; else { temp=b[i]; b[i]=b[j]; b[j]=temp; } } } void main() { int a[N]={0},i; clrscr(); printf("please input no more than %d int datas:\n",N); for(i=0;i scanf("%d",&a[i]); taxis(a,N); printf("The result of taxis is:\n"); for(i=0;i { printf("%d",a[i]); if(a[i+1]==0&&a[i+2]==0&&a[i+3]==0) break; printf(","); } } /*将整型数组的元素进行简单选择排序(终端输入的整型排序-指针),如果连续出现3个为0的数据,*/ /*则默认判断这3个为0的数据以和其后面是没有数据,*/ /*即不输出这3个为0的数据以和其后面的数据(元素来自终端)*/ #include #include #define N 50 void taxis(int *p1,int k) { int temp,*p2,*p3; for(p2=p1;p2 for(p3=p2+1;p3 if(*p2>*p3) { if(*p3==0&&*(p3+1)==0&&*(p3+2)==0) break; else { temp=*p2; *p2=*p3; *p3=temp; } } } void main() { int a[N]={0},*p; clrscr(); printf("please input no more than %d int datas:\n",N); for(p=a;p scanf("%d",p); taxis(a,N); printf("The result of is:\n"); for(p=a;p { printf("%d",*p); if(*(p+1)==0&&*(p+2)==0&&*(p+3)==0) break; printf(","); } } /*将字符串按字母顺序(字母对应的ASCⅡ值由小到大)进行简单选择排序(终端输入的字符串顺序排序)*/ /*当输入字符串时,遇到"回车"键则表示该字符串输入结束;当连续输入两个"回车键"时,则表示所有字符串输入结束*/ #include #include #include #define N 50 #define size 15 void taxis(char *p1[],int k) { int i,j; char *temp; for(i=0;i for(j=i+1;j if(strlen(p1[i])>strlen(p1[j])&&strlen(p1[j])!=0) { temp=p1[i]; p1[i]=p1[j]; p1[j]=temp; } } void main() { char a[size]={0},*p[N]={0}; int i; clrscr(); printf("Please input no more than %d strings\n",N); for(i=0;i { gets(a); if(strlen(a)==0) break; p[i]=(char*)calloc(sizeof(a),sizeof(char)); strcpy(p[i],a); } taxis(p,N); printf("The result of taxis is:\n"); for(i=0;i { if(strlen(p[i])==0) break; printf("%s\n",p[i]); } } /*将字符串按字母顺序(字母对应的ASCⅡ值由小到大)进行简单选择排序(终端输入的字符串顺序排序)*/ /*当输入字符串时,遇到"回车"键则表示该字符串输入结束;当连续输入两个"回车键"时,则表示所有字符串输入结束*/ #include #include #include #define N 50 #define size 15 void taxis(char *p1[],int k) { int i,j; char *temp; for(i=0;i for(j=i+1;j if(strcmp(p1[i],p1[j])>0&&strlen(p1[j])!=0) { temp=p1[i]; p1[i]=p1[j]; p1[j]=temp; } } void main() { char a[size]={0},*p[N]={0}; int i; clrscr(); printf("Please input no more than %d strings\n",N); for(i=0;i { gets(a); if(strlen(a)==0) break; p[i]=(char*)calloc(sizeof(a),sizeof(char)); strcpy(p[i],a); } taxis(p,N); printf("The result of taxis is:\n"); for(i=0;i { if(strlen(p[i])==0) break; printf("%s\n",p[i]); } } 选择排序 /*对整型数组的元素进行选择排序(源程序的整型排序)*/ #include #include #define N 6 void taxis(int b[],int k) { int i,j,n,temp; for(i=0;i { n=i; for(j=i+1;j if(b[n]>b[j]) n=j; if(n!=i) { temp=b[i]; b[i]=b[n]; b[n]=temp; } } } void main() { int a[N]={9,8,5,6,2,0},i; clrscr(); taxis(a,N); for(i=0;i { printf("%d",a[i]); if(i printf(","); } } /*对整型数组的元素进行选择排序(源程序的整型排序-指针))*/ #include #include #define N 6 void taxis(int *p1,int k) { int i,temp,*p2,*p3; for(i=0;i { p2=p1+i; for(p3=p1+i+1;p3 if(*p2>*p3) p2=p3; if(p2!=p1+i) { temp=*(p1+i); *(p1+i)=*p2; *p2=temp; } } } void main() { int a[N]={9,8,5,6,2,0},*p; clrscr(); taxis(a,N); for(p=a;p { printf("%d",*p); if(p printf(","); } } /*将字符串按其的长度(字母对应的ASCⅡ值由小到大)进行选择排序(源程序的字符串长度排序)*/ #include #include #include #define N 5 void taxis(char **p1,int k) { int i; char **p2,**p3,**temp; for(i=0;i { p2=p1+i; for(p3=p1+i+1;p3 if(strlen(*p2)>strlen(*p3)) p2=p3; if(p2!=p1+i) { *temp=*(p1+i); *(p1+i)=*p2; *p2=*temp; } } } void main() { char *a[]={"Follow","BASIC","Great","FORTRAN","Computer"}; int i; clrscr(); taxis(a,N); printf("The result of taxis is:\n"); for(i=0;i printf("%s\n",a[i]); } /*将字符串按字母顺序(字母对应的ASCⅡ值由小到大)进行选择排序(源程序的字符串顺序排序)*/ #include #include #include #define N 5 void taxis(char **p1,int k) { int i; char **p2,**p3,**temp; for(i=0;i { p2=p1+i; for(p3=p1+i+1;p3 if(strcmp(*p2,*p3)>0) p2=p3; if(p2!=p1+i) { *temp=*(p1+i); *(p1+i)=*p2; *p2=*temp; } } } void main() { char *a[]={"Follow","BASIC","Great","FORTRAN","Computer"}; int i; clrscr(); taxis(a,N); for(i=0;i printf("%s\n",a[i]); } /*将整型数组的元素进行选择排序(终端输入的整型排序),如果连续出现3个为0的数据,*/ /*则默认判断这3个为0的数据无效以和其后面是没有数据,*/ /*即不输出这3个为0的数据以和其后面的数据(元素来自终端)*/ #include #include #define N 10 void taxis(int b[],int k) { int i,j,n,temp; for(i=0;i { n=i; for(j=i+1;j if(b[n]>b[j]) { if(b[j]==0&&b[j+1]==0&&b[j+2]==0) break; else n=j; } if(n!=i) { temp=b[i]; b[i]=b[n]; b[n]=temp; } } } void main() { int a[N]={0},i; clrscr(); printf("please input no more than %d int datas:\n",N); for(i=0;i scanf("%d",&a[i]); taxis(a,N); printf("The result of taxis is:\n"); for(i=0;i { printf("%d",a[i]); if(a[i+1]==0&&a[i+2]==0&&a[i+3]==0) break; printf(","); } } /*将整型数组的元素进行选择排序(终端输入的整型排序-指针),如果连续出现3个为0的数据,*/ /*则默认判断这3个为0的数据以和其后面是没有数据,*/ /*即不输出这3个为0的数据以和其后面的数据(元素来自终端)*/ #include #include #define N 50 void taxis(int *p1,int k) { int i,temp,*p2,*p3; for(i=0;i { p2=p1+i; for(p3=p1+i+1;p3 if(*p2>*p3) { if(*p3==0&&*(p3+1)==0&&*(p3+2)==0) break; else p2=p3; } if(p2!=p1+i) { temp=*(p1+i); *(p1+i)=*p2; *p2=temp; } } } void main() { int a[N]={0},*p; clrscr(); printf("please input no more than %d int datas:\n",N); for(p=a;p scanf("%d",p); taxis(a,N); printf("The result of is:\n"); for(p=a;p { printf("%d",*p); if(*(p+1)==0&&*(p+2)==0&&*(p+3)==0) break; printf(","); } } /*将字符串按字母顺序(字母对应的ASCⅡ值由小到大)进行选择排序(终端输入的字符串顺序排序)*/ /*当输入字符串时,遇到"回车"键则表示该字符串输入结束;当连续输入两个"回车键"时,则表示所有字符串输入结束*/ #include #include #include #define N 50 #define size 15 void taxis(char **p1,int k) { int i; char **p2,**p3,**temp; for(i=0;i { p2=p1+i; for(p3=p1+i+1;p3 if(strlen(*p2)>strlen(*p3)&&strlen(*p3)!=0) if(p2!=p1+i) { *temp=*(p1+i); *(p1+i)=*p2; *p2=*temp; } } } void main() { char a[size]={0},*p[N]={0}; int i; clrscr(); printf("Please input no more than %d strings\n",N); for(i=0;i { gets(a); if(strlen(a)==0) break; p[i]=(char*)calloc(sizeof(a),sizeof(char)); strcpy(p[i],a); } taxis(p,N); printf("The result of taxis is:\n"); for(i=0;i { if(strlen(p[i])==0) break; printf("%s\n",p[i]); } } /*将字符串按字母顺序(字母对应的ASCⅡ值由小到大)进行选择排序(终端输入的字符串顺序排序)*/ /*当输入字符串时,遇到"回车"键则表示该字符串输入结束;当连续输入两个"回车键"时,则表示所有字符串输入结束*/ #include #include #include #define N 50 #define size 15 void taxis(char **p1,int k) { int i; char **p2,**p3,**temp; for(i=0;i { p2=p1+i; for(p3=p1+i+1;p3 if(strcmp(*p2,*p3)>0&&strlen(*p3)!=0) p2=p3; if(p2!=p1+i) { *temp=*(p1+i); *p2=*temp; } } } void main() { char a[size]={0},*p[N]={0}; int i; clrscr(); printf("Please input no more than %d strings\n",N); for(i=0;i { gets(a); if(strlen(a)==0) break; p[i]=(char*)calloc(sizeof(a),sizeof(char)); strcpy(p[i],a); } taxis(p,N); printf("The result of taxis is:\n"); for(i=0;i { if(strlen(p[i])==0) break; printf("%s\n",p[i]); } } 起泡排序/*对整型数组的元素进行起泡排序(源程序的整型排序)*/ #include #include #define N 6 void taxis(int b[],int k) { int i,j,temp; for(i=0;i for(j=0;j if(b[j]>b[j+1]) { temp=b[j]; b[j]=b[j+1]; b[j+1]=temp; } } void main() { int a[N]={9,8,5,6,2,0},i; clrscr(); taxis(a,N); for(i=0;i { printf("%d",a[i]); if(i printf(","); } } /*对整型数组的元素进行起泡排序(源程序的整型排序-指针))*/ #include #include #define N 6 void taxis(int *p1,int k) { int i,temp,*p2; for(i=0;i { for(p2=p1;p2 if(*p2>*(p2+1)) { temp=*p2; *p2=*(p2+1); *(p2+1)=temp; } } } void main() { int a[N]={9,8,5,6,2,0},*p; clrscr(); taxis(a,N); for(p=a;p { printf("%d",*p); if(p printf(","); } } /*将字符串按其的长度(字母对应的ASCⅡ值由小到大)进行起泡排序(源程序的字符串长度排序)*/ #include #include #include #define N 5 void taxis(char **p1,int k) { int i; char **p2,**temp; for(i=0;i for(p2=p1;p2 if(strlen(*p2)>strlen(*(p2+1))) { *temp=*p2; *p2=*(p2+1); *(p2+1)=*temp; } } void main() { char *a[]={"Follow","BASIC","Great","FORTRAN","Computer"}; int i; clrscr(); taxis(a,N); printf("The result of taxis is:\n"); for(i=0;i printf("%s\n",a[i]); } /*将字符串按字母顺序(字母对应的ASCⅡ值由小到大)进行起泡排序(源程序的字符串顺序排序)*/ #include #include #include #define N 5 void taxis(char **p1,int k) { int i; char **p2,**temp; for(i=0;i for(p2=p1;p2 if(strcmp(*p2,*(p2+1))>0) { *temp=*p2; *p2=*(p2+1); *(p2+1)=*temp; } } void main() { char *a[]={"Follow","BASIC","Great","FORTRAN","Computer"}; int i; clrscr(); taxis(a,N); for(i=0;i printf("%s\n",a[i]); } /*将整型数组的元素进行起泡排序(终端输入的整型排序),如果连续出现3个为0的数据,*/ /*则默认判断这3个为0的数据无效以和其后面是没有数据,*/ /*即不输出这3个为0的数据以和其后面的数据(元素来自终端)*/ #include #include #define N 50 void taxis(int b[],int k) { int i,j,temp; for(i=0;i for(j=0;j if(b[j]>b[j+1]) { if(b[j+1]==0&&b[j+2]==0&&b[j+3]==0) break; else { temp=b[j]; b[j]=b[j+1]; b[j+1]=temp; } } } void main() { int a[N]={0},i; clrscr(); printf("please input no more than %d int datas:\n",N); for(i=0;i scanf("%d",&a[i]); taxis(a,N); printf("The result of taxis is:\n"); for(i=0;i { printf("%d",a[i]); if(a[i+1]==0&&a[i+2]==0&&a[i+3]==0) break; printf(","); } } /*将整型数组的元素进行起泡排序(终端输入的整型排序-指针),如果连续出现3个为0的数据,*/ /*则默认判断这3个为0的数据以和其后面是没有数据,*/ /*即不输出这3个为0的数据以和其后面的数据(元素来自终端)*/ #include #include #define N 50 void taxis(int *p1,int k) { int i,temp,*p2; for(i=0;i for(p2=p1;p2 if(*p2>*(p2+1)) { if(*(p2+1)==0&&*(p2+2)==0&&*(p2+3)==0) break; else { temp=*p2; *p2=*(p2+1); *(p2+1)=temp; } } } void main() { int a[N]={0},*p; clrscr(); printf("please input no more than %d int datas:\n",N); for(p=a;p scanf("%d",p); taxis(a,N); printf("The result of taxis is:\n"); for(p=a;p { printf("%d",*p); if(*(p+1)==0&&*(p+2)==0&&*(p+3)==0) break; printf(","); } } /*将字符串按字母顺序(字母对应的ASCⅡ值由小到大)进行起泡排序(终端输入的字符串顺序排序)*/ /*当输入字符串时,遇到"回车"键则表示该字符串输入结束;当连续输入两个"回车键"时,则表示所有字符串输入结束*/ #include #include #include #define N 50 #define size 15 void taxis(char **p1,int k) { int i; char **p2,**temp; for(i=0;i for(p2=p1;p2 if(strlen(*p2)>strlen(*(p2+1))&&strlen(*(p2+1))!=0) { *temp=*p2; *p2=*(p2+1); *(p2+1)=*temp; } } void main() { char a[size]={0},*p[N]={0}; int i; clrscr(); printf("Please input no more than %d strings\n",N); for(i=0;i { gets(a); if(strlen(a)==0) break; p[i]=(char*)calloc(sizeof(a),sizeof(char)); strcpy(p[i],a); } taxis(p,N); printf("The result of taxis is:\n"); for(i=0;i { if(strlen(p[i])==0) break; printf("%s\n",p[i]); } } /*将字符串按字母顺序(字母对应的ASCⅡ值由小到大)进行起泡排序(终端输入的字符串顺序排序)*/ /*当输入字符串时,遇到"回车"键则表示该字符串输入结束;当连续输入两个"回车键"时,则表示所有字符串输入结束*/ #include #include #include #define N 50 #define size 15 void taxis(char **p1,int k) { int i; char **p2,**temp; for(i=0;i for(p2=p1;p2 if(strcmp(*p2,*(p2+1))>0&&strlen(*(p2+1))!=0) { *temp=*p2; *p2=*(p2+1); *(p2+1)=*temp; } } void main() { char a[size]={0},*p[N]={0}; int i; clrscr(); printf("Please input no more than %d strings\n",N); for(i=0;i { gets(a); if(strlen(a)==0) break; p[i]=(char*)calloc(sizeof(a),sizeof(char)); strcpy(p[i],a); } taxis(p,N); printf("The result of taxis is:\n"); for(i=0;i { if(strlen(p[i])==0) break; printf("%s\n",p[i]); } } 快速排序 //C语言中的快速排序 //从终端输入不多于N个整型数据，然后将它们进行选择排序(从小到大),如果连续输入3个为0的数据, //则默认判断这3个为0的数据无效以和其后面是没有数据,*/ //即不输出这3个为0的数据以和其后面的数据 #include #define N 20 void quick_sort(int data[], int low, int high) { int i, j, pivot; if (low < high) { pivot=data[low]; i=low; j=high; while(i { while (i j--; if(i data[i++]=data[j]; while (i i++; if(i data[j--]=data[i]; } data[i]=pivot; quick_sort(data,low,i-1); quick_sort(data,i+1,high); } } int input_data(int data[]) { int i,k; k=0; for(i=0;i { scanf("%d",&data[i]); k++; if(k>=3&&data[i]==0&&data[i-1]==0&&data[i-2]==0) { k-=3; break; } } return k; } void output_data(int data[],int m) { int i; printf("The result of taxis is:\n"); for(i=0;i { printf("%d",data[i]); if(i+1 printf(","); if((i+1)%10==0) printf("\n"); } printf("\n"); } void main() { int n,data[N]={0}; printf("please input no more than %d int datas:\n",N); n=input_data(data); quick_sort(data,0,n-1); output_data(data,n); } C语言几种常见的排序方法 2009-04-2219:55 插入排序是这样实现的： 首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。 从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。 重复2号步骤，直至原数列为空。 插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的： 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。 重复2号步骤，直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。 选择排序 选择排序是这样实现的： 设数组内存放了n个待排数字，数组下标从1开始，到n结束。 i=1 从数组的第i个元素开始到第n个元素，寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n－1算法结束，否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同，它是这样的： 首先新建一个空列表，作用与插入排序中的"有序列表"相同。 找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。 重复2号步骤，直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。 C语言9种常用排序法 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.带哨兵的直接插入排序 9.基数排序 例子：乱序输入n个数，输出从小到大排序后的结果1.冒泡排序 #include for(i=0;i int i, j, n, a[100], t, temp; while(scanf("%d",&n)!=EOF) { for(i=0;i 简单选择排序 /*对整型数组的元素进行简单选择排序(源程序的整型简单选择排序)*/ #include printf("%d",*p); if(p 关于本周学习汇总 1起泡排序： 过程：首先将第一个记录的关键字和第二字的关键字进行比较，若为逆序，则将两个记录交换。然后再比较第二个记录跟第三个记录关键字。以此类推，直到第n-1个记录和第n个记录关键字进行比较为止。这样做出了第一趟排序。其结果是使得最大的数在第n的记录。然后对前n-1的记录进行同样的操作。结果得出次大的大在n-1记录上。最后直到只有第1个和第2个记录进行比较后，完成所有的排序。由此可以看出需要进行k（1<=k #i n c l u d e #include if(i 常见经典排序算法（C语言） 1.希尔排序 2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序 一.希尔（Shell）排序法（又称宿小增量排序，是1959年由D.L.Shell提出来的） /* Shell 排序法*/ #include } } 二.二分插入法 /* 二分插入法*/ void HalfInsertSort(int a[], int len) { int i, j,temp; int low, high, mid; for (i=1; i C语言实现各种排序方法： 1.快速排序： #include right--; } } if(left kuai_pai(a,0,n-1); printf("排序后为：\n"); for(i=0;i!=n;++i) printf("%d ",a[i]); printf("\n"); free(a); } 2.shell排序 #include (一)基本思想 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： ①初始状态：无序区为R[1..n]，有序区为空。 ②第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 …… ③第i趟排序 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 [编辑本段]排序过程 【示例】： 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 65 76] 第六趟排序后13 27 38 49 49 65 [97 76] 第七趟排序后13 27 38 49 49 76 [97 76] 最后排序结果13 27 38 49 49 76 76 97 (二)C语言过程 void selectionSort(Type* arr,long len) { long i=0,j=0;/*iterator value*/ long maxPos; assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n"); for(i=len-1;i>=1;i--) { maxPos=i; for(j=0;j 一插入排序 1.1 直接插入排序 基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。 图解： 1.//直接顺序排序 2.void InsertSort(int r[], int n) 3.{ 4.for (int i=2; i 代码实现： [cpp]view plain copy 1.//希尔排序 2.void ShellSort(int r[], int n) 3.{ 4.int i; 5.int d; 6.int j; 7.for (d=n/2; d>=1; d=d/2) //以增量为d进行直接插入排序 8. { 9.for (i=d+1; i C语言排序总汇 1、插入法排序 算法如下： voidInsertsort(int n) { inti,j; for(i=2;i<=n;i++) /*依次插入R[2],R[3],.....R[n]*/ if(R[i] voidInsertsort(int n) { inti,j; for(i=2;i<=n;i++) /*依次插入R[2],R[3],.....R[n]*/ if(R[i] 《高级语言程序设计》 课程设计报告 题目： 排序算法 专业： 班级： 姓名： 指导教师： 成绩： 计算机与信息工程系 2015年3月26日 2014-2015学年 第2学期 目录 引言 (1) 需求分析 (1) 第一章程序内容及要求 (1) 1.1 冒泡排序 (1) 1.2 选择排序 (2) 1.3 插入排序 (3) 第二章概要设计 (4) 2.1冒泡排序 (4) 2.2选择排序 (5) 2.3插入排序 (6) 第三章程序的比较及其应用 (7) 3.1时间复杂度 (7) 3.2空间复杂度 (7) 3.3稳定程度 (7) 3.4应用及其改进 (8) 第四章程序设计结果 (8) 附录 (9) 参考文献 (12) 引言 伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员来说，这将是一个挑战。 经常查找资料的朋友都会知道，面对海量的资料，如果其查找资料没有进行排序，那么其查找资料将会是一家非常痛苦的事情。针对这一问题，我们自此通过一个课程设计来解决它。 理论上排序算法有很多种，不过本课程设计只涉及到三种算法。这三种算法包括：冒泡排序，选择排序，直接插入排序。 本课程设计通过对这三种算法的运行情况进行对比，选择最优秀的算法出来。希望通过我的努力能解决一些问题，带来一些方便。 需求分析 本课程题目是排序算法的实现，由于各方面的原因，本科程设计一共需要设计三种排序算法。这三种算法包括：冒泡排序，选择排序，直接插入排序。三种排序算法各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。 由于使用的调试软件及操作系统不一样。因此个别程序在不同的软件上可能会报错。 本课程软件运行的的操作系统为Windows7 64位操作系统。所使用的软件为Microsoft Visual C++6.0以及Turbo C2.0 第一章程序内容及要求 1.1 冒泡排序 冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。 /* ===================================================================== ======== 相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）： 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就 说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4, a2,a3,a5就不是稳定的了。 2、内排序和外排序 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ===================================================================== =========== */ /* ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述： #include } }/*BinSort*/ //希尔排序 void ShellSort(recdtype R[],int n) { int i,j; for(int d=N/2;d>=1;d=d/2) { for(i=1+d;i<=n;i++) { R[0]=R[i]; j=i-d; while(j>0&&R[0].key #include int indegree; //入度 }VexNode; //顶点边定义 typedef struct LGraph { VexNode vex_array[Max]; //顶点数组 int vexnum; //图中顶点数 }LGraph; /*函数功能：图的创建 入口参数：图G 返回值：无 */ void Creat_G(Graph *G) { char v; int i=0; int j=0; G->vexnum=0; printf("输入说明。。。有权值请输入权值，无权值请输入1，无边请输入0\n"); printf("\n请输入所有顶点(不超过20个，按‘#’结束输入)：\n"); do{ printf("输入第%d 个顶点：",G->vexnum+1); scanf(" %c",&v); G->vex_array[G->vexnum].data = v; G->vexnum++; }while(v!='#'); G->vexnum--; printf("输入邻接矩阵（%d * %d）：",G->vexnum,G->vexnum); for(i=0; i 选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进行升序排列，算法步骤是： 1、从数组存放的n个数中找出最小数的下标（算法见下面的“求最值”），然后将最小数与第1个数交换位置； 2、除第1个数以外，再从其余n-1个数中找出最小数（即n个数中的次小数）的下标，将此数与第2个数交换位置； 3、重复步骤1 n-1趟，即可完成所求。 好了，接下来看代码: 1.#include 直接插入排序 算法思想简单描述： 在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。 直接插入排序是稳定的。算法时间复杂度O(n^2) 算法实现： /* 功能：直接插入排序 输入：数组名称（也就是数组首地址）、数组中元素个数 */ void insert_sort(int *x, int n) { int i, j, t; for (i=1; i */ t=*(x+ I ); for (j=i-1; j>=0 && t<*(x+j); j--) /*注意：j=i-1，j--，这里就是下标为i的数，在它前面有序列中找插入位置。*/ { *(x+j+1) = *(x+ j ); /*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小，它要放在最前面，j==-1，退出循环*/ } *(x+j+1) = t; /*找到下标为i的数的放置位置*/ } } #include "stdio.h" #include "conio.h" main() { int a[11]={1,4,6,9,13,16,19,28,40,100}; int temp1,temp2,number,end,i,j; printf("original array is:\n"); for(i=0;i<10;i++) printf("%5d",a[i]); printf("\n"); printf("insert a new number:"); scanf("%d",&number); end=a[9]; if(number>end) a[10]=number; else { for(i=0;i<10;i++) { if(a[i]>number) { temp1=a[i]; a[i]=number; for(j=i+1;j<11;j++) { temp2=a[j]; a[j]=temp1; temp1=temp2; } break; } } } for(i=0;i<11;i++) printf("%6d",a[i]); getch(); #include 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。 2、内排序和外排序在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ==================================================== 算法思想简单描述： 在要排序的一组数中，选出最小的一个数与第一个位置的数交换； 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环 到倒数第二个数和最后一个数比较为止。 选择排序是不稳定的。算法复杂度O(n2)--[n的平方] ===================================================== void select_sort(int*x,int n) { int i,j,min,t; for(i=0;i /******************************************************* 三种基本排序演示程序 说明：此程序适用于理解三种基本排序原理（简单排序，选择排序，插入排序）以及排序的每一个步骤。并且在重要部分有注释. 本人是一家计算机培训机构的兼职教师（培训计算机C二级的），看到许多同学对于排序非常头疼，当然这是二级C的必考点之一，也是贯穿C语言各种知识点的拿分大项。 本程序是自己按照原理写的原创代码，所以定为1分吧（辛苦费吧，一般我搜集的都是免费的(*^__^*) ……，望大家支持下） 此程序我调试运行成功的，如果你复制到编译器不成功，可能是编译器区别造成的。 如果能自己写出这三种排序的同学，我觉得其对C语言基础知识学习就比较牢固了。 时间：2012年12月3日 ********************************************************/ #includeC语言几种常见的排序方法
C语言9种常用排序法
C语言的四种排序
c语言的三种排序(冒泡,快速,选择)
c语言各种排序方法及其所耗时间比较程序
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排
c语言实现各种排序程序
C语言 选择排序
c语言各种排序法详细讲解
C语言排序总汇
c语言程序设计(排序算法)
C语言常用排序算法
C语言综合实现所有排序方法及效率比较
各种排序算法C语言实现
C语言之选择排序
排序算法C语言版：直接插入排序
c语言实现简单排序(8种方法)
C语言常用排序算法
C语言三种基本排序(简单排序,选择排序,插入排序)演示程序(含注释、每一个步骤,原创) -修订