- #include <stdio.h>
- #include <stdlib.h>
- #define N 10
- int sort[N+1],befsort[N+1]={23,29,18,89,5,0,35,23,67,78};
- void Dir_insert_sort()
- {
- int i,j;
- for(i=1; i<N; i++)
- if(sort[i]<sort[i-1])
- {
- sort[N]=sort[i];
- j=i-1;
- do{
- sort[j+1]=sort[j];
- j-- ;
- }while(sort[N]<sort[j]);
- sort[j+1]=sort[N];
- }
- }
- void Bin_insert_sort()
- {
- int middle=0;
- for(int i = 0; i < N; i++)
- {
- int low = 0;
- int high = i-1;
- int temp = sort[i];
- while(low <= high)
- {
- middle = (low + high) / 2;
- if(temp < sort[middle])
- high = middle - 1;
- else
- low = middle + 1;
- }
- for(int k = i; k >middle; k--)
- sort[k] = sort[k-1 ];
- sort[low] = temp ;
- }
- }
- void Hill_sort()
- {
- int i,j,x,d;
- d= N / 2;
- while (d>=1)
- {
- for (i=d;i<N;i++)
- {
- x=sort[i];
- j=i-d;
- while (j>=0 && x<sort[j])
- {
- sort[j+d]=sort[j];
- j-=d;
- }
- sort[j+d]=x;
- }
- d /= 2;
- }
- }
- void Bubble_sort()
- {
- int i,j,temp,flag=1;
- for(i=0; i<N && flag; i++)
- {
- flag=0;
- for(j=0; j<N-1; j++)
- {
- if(sort[j]>sort[j+1])
- {
- temp = sort[j];
- sort[j]=sort[j+1];
- sort[j+1]=temp;
- flag=1;
- }
- }
- }
- }
- int part(int p,int r)
- {
- int x=sort[r],i=p-1,j,t;
- for(j=p;j<r;j++)
- {
- if(sort[j]<=x)
- {
- i++;
- t=sort[i];
- sort[i]=sort[j];
- sort[j]=t;
- }
- }
- t=sort[i+1];
- sort[i+1]=sort[r];
- sort[r]=t;
- return(i+1);
- }
- void Quick_sort(int p,int r)
- {
- if(p<r)
- {
- int q=part(p,r);
- Quick_sort(p,q-1);
- Quick_sort(q+1,r);
- }
- }
- void Dir_select_sort()
- {
- int i,k,swap;
- for (i = 1; i < N; i++)
- {
- k = i - 1;
- swap = 0;
- for (int j = i; j < N; j++)
- {
- if (sort[j] < sort[k])
- {
- k = j;
- }
- }
- if (k != i-1)
- {
- swap = sort[i - 1];
- sort[i - 1] = sort[k];
- sort[k] = swap;
- }
- }
- }
- void heap(int a[], int i, int n)
- {
- int largest,l=2*i+1,r=2*i+2;
- if(l<=n-1&&a[l]>a[i])
- largest=l;
- else
- largest=i;
- if(r<=n-1&&a[r]>a[largest])
- largest=r;
- if(largest!=i){
- int t=a[i];
- a[i]=a[largest];
- a[largest]=t;
- heap(a,largest,n);}
- }
- void build_heap(int a[],int n)
- {
- for(int i=(n-1)/2;i>=0;i--)
- heap(a,i,n);
- }
- void Heap_sort(int a[],int n)
- {
- build_heap(a,N);
- for(int i=N-1; i>0; i--)
- {
- int t=sort[0];
- sort[0]=sort[i];
- sort[i]=t;
- heap(a,0,--n);
- }
- }
- void merg(int b[],int p,int i,int r)
- {
- int m=p,n=i+1,k=p;
- while(m<=i&&n<=r){
- if(sort[m]<sort[n])
- b[k++]=sort[m++];
- else
- b[k++]=sort[n++];}
- if(m>i)
- for(int t=n;t<=r;t++)
- b[k++]=sort[t];
- else
- for(int t=m;t<=i;t++)
- b[k++]=sort[t];
- }
- void Merge_sort(int p,int r)
- {
- if(p<r)
- {
- int i=(p+r)/2;
- int *b=new int[sizeof(sort)];
- Merge_sort(p,i);
- Merge_sort(i+1,r);
- merg(b,p,i,r);
- for(int t=p;t<=r;t++)
- sort[t]=b[t];
- }
- }
- void Radix_sort()
- {
- int temp[N][N]={0};
- int order[N]={0};
- int i,j,k=0,m=1,lsd;
- while (m<=10)
- {
- for (i=0;i<N;i++)
- {
- lsd=((sort[i]/m)%10);
- temp[lsd][order[lsd]]=sort[i];
- order[lsd]++;
- }
- for (i=0;i<10;i++)
- {
- if(order[i] != 0)
- for (j=0;j<order[i];j++)
- {
- sort[k]=temp[i][j];
- k++;
- }
- order[i]=0;
- }
- m *= 10;
- k=0;
- }
- }
- void showFace()
- {
- system("cls");
- printf(" **********排序算法********** \\n");
- printf(".....................(本系统按从小到大排序).....................\\n");
- printf("................................................................\\n");
- printf(" 1:直接插入排序 2:折半插入排序\\n");
- printf(" 3:希尔排序 4:冒泡排序 \\n");
- printf(" 5:快速排序 6:直接选择排序\\n");
- printf(" 7:堆排序 8:归并排序 \\n");
- printf(" 9:基数排序 q:退出系统 \\n");
- printf("*****************************************************************\\n");
- printf("请输入你要执行的操作:\\n");
- }
- void run()
- {
- int i;
- char MyOperation;
- scanf("%c",&MyOperation);
- getchar();
- while (MyOperation!='q')
- {
- switch(MyOperation)
- {
- case '1':
- {
- printf("调用直接插入排序前: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",befsort[i]);
- sort[i]=befsort[i];
- }
- Dir_insert_sort();
- printf("\\n调用直接插入排序后: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",sort[i]);
- }
- printf("\\n按“Enter”键返回\\n");
- break;
- }
- case '2':
- {
- printf("调用折半插入排序前: ");
- for(i=0;i<N;i++)
- {
- sort[i]=befsort[i];
- printf("%d ",befsort[i]);
- }
- Bin_insert_sort();
- printf("\\n调用折半插入排序后: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",sort[i]);
- }
- printf("\\n按“Enter”键返回\\n");
- break;
- }
- case '3':
- {
- printf("调用希尔排序前: ");
- for(i=0;i<N;i++)
- {
- sort[i]=befsort[i];
- printf("%d ",befsort[i]);
- }
- Hill_sort();
- printf("\\n调用希尔排序后: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",sort[i]);
- }
- printf("\\n按“Enter”键返回\\n");
- break;
- }
- case '4':
- {
- printf("调用冒泡排序前: ");
- for(i=0;i<N;i++)
- {
- sort[i]=befsort[i];
- printf("%d ",befsort[i]);
- }
- Bubble_sort();
- printf("\\n调用冒泡排序后: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",sort[i]);
- }
- printf("\\n按“Enter”键返回\\n");
- break;
- }
- case '5':
- {
- printf("调用快速排序前: ");
- for(i=0;i<N;i++)
- {
- sort[i]=befsort[i];
- printf("%d ",befsort[i]);
- }
- Quick_sort(0,N-1);
- printf("\\n调用快速排序后: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",sort[i]);
- }
- printf("\\n按“Enter”键返回\\n");
- break;
- }
- case '6':
- {
- printf("调用直接选择排序前: ");
- for(i=0;i<N;i++)
- {
- sort[i]=befsort[i];
- printf("%d ",befsort[i]);
- }
- Dir_select_sort();
- printf("\\n调用直接选择排序后: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",sort[i]);
- }
- printf("\\n按“Enter”键返回\\n");
- break;
- }
- case '7':
- {
- printf("调用堆排序前: ");
- for(i=0;i<N;i++)
- {
- sort[i]=befsort[i];
- printf("%d ",befsort[i]);
- }
- Heap_sort(sort,N);
- printf("\\n调用堆排序后: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",sort[i]);
- }
- printf("\\n按“Enter”键返回\\n");
- break;
- }
- case '8':
- {
- printf("调用归并排序前: ");
- for(i=0;i<N;i++)
- {
- sort[i]=befsort[i];
- printf("%d ",befsort[i]);
- }
- Merge_sort(0,N-1);
- printf("\\n调用归并排序后: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",sort[i]);
- }
- printf("\\n按“Enter”键返回\\n");
- break;
- }
- case '9':
- {
- printf("调用基数排序前: ");
- for(i=0;i<N;i++)
- {
- sort[i]=befsort[i];
- printf("%d ",befsort[i]);
- }
- Radix_sort();
- printf("\\n调用基数排序后: ");
- for(i=0;i<N;i++)
- {
- printf("%d ",sort[i]);
- }
- printf("\\n按“Enter”键返回\\n");
- break;
- }
- default:
- {
- printf("请选择1~9\\n按“Enter”键返回\\n");
- }
- }
- getchar();
- showFace();
- scanf("%c",&MyOperation);
- getchar();
- }
- }
- int main()
- {
- showFace();
- run();
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/090520149507.html
来源: http://www.codesnippet.cn/detail/090520149507.html