#include <stdio.h>
#include <time.h>
#include<stdlib.h>
#include<dos.h>
#define n 10000
typedef int keytype;
typedef struct{
    keytype key;
  }rectype;//待排序的文件的记录类型
typedef rectype seqlist[n+1];
seqlist r;
int m;
main()//主程序
  {
　　int i,j;

　　//选择一种数据输入形式
　　printf("1---random data\n");
　　printf("2---inscre data\n");
　　printf("3---descre data\n");
　　printf("4---input data\n");
　　scanf("%d",&j);
　　if (j==1) randoming();//产生一组随机数据

　　if (j==2)//产生一组递增序列
　　　for (m=1;m<=n;m++)
　　　　r[m].key=m;

　　if (j==3)//产生一组递减序列
　　　for(m=1;m<=n;m++)
　　　　r[m].key=n-m+1;

　　if (j==4){//由用户自己输入数据序列，设这组数据中不含0，以0作为结束
　　　　printf("please input the sort data:(end of 0)\n");
　　　　r[0].key=1;
　　　　m=0;
　　　　while((m<=n)&&(r[m].key)){
　　　　　　m++;
　　　　　　scanf("%d",&(r[m].key));
　　　　　}//end of while
　　　　m--;
　　　}//end of if

　　printf("1-----insertsort\n");
　　printf("2-----bubblesort\n");
　　printf("3-----selectsort\n");
　　printf("4-----quicksort\n");
　　printf("5-----heapsort\n");
　　scanf("%d",&j);

　　//输出排序前的序列
　　printf("the source data:\n");
　　for(i=1;i<=m;i++)
　　　printf("%d ",r[i].key);
　　printf("\n");

　　//选择一种方法进行排序
　　if (j==1) insertsort(m);//直接插入排序
　　if (j==2) bubblesort(m);//冒泡排序
　　if (j==3) selectsort(m);//直接选择排序
　　if (j==4) quicksort(1,m);//快速排序
　　//if (j==5) heapsort(m);//堆排序

　　//以下输出排序结果
　　printf("the answer data:\n");
　　for(i=1;i<=m;i++)
　　　　printf("%d ",r[i].key);
　}//end of main


　insertsort(int m)
　　{//直接插入排序
　　　int i,j;
　　　for(i=2;i<=m;i++)
　　　　if (r[i].key<r[i-1].key){
　　　　　　r[0].key=r[i].key;j=i-1;
　　　　　　do{
　　　　　　　　　r[j+1].key=r[j].key;
　　　　　　　　　j--;
　　　　　　　}while (r[0].key<r[j].key);
　　　　　　r[j+1].key=r[0].key;
　　　　　}//end of if
　　}//end of insertsort

　bubblesort(int m){
　　　//冒泡排序
　　　int i,j;
　　　int exchange;
　　　for(i=1;i<m;i++){
　　　　　exchange=0;//设置未交换过标记
　　　　　for(j=m-1;j>=1;j--)
　　　　　　if(r[j+1].key<r[j].key){//若逆序
　　　　　　　　r[0].key=r[j+1].key;//以r[0]为辅助空间交换
　　　　　　　　r[j+1].key=r[j].key;
　　　　　　　　r[j].key=r[0].key;
　　　　　　　　exchange=1;//设置做过交换标志
　　　　　　　}//end of if
　　　　　if (!exchange) return;
　　　　}//end of for
　　}//end of bubblesort

　selectsort(int m)
　　　{//直接选择排序
　　　　int i,j,k;
　　　　for(i=1;i<m;i++){
　　　　　　k=i;
　　　　　　for(j=i+1;j<=m;j++)//在无序区r[j..m]中查找最小关键字位置k
　　　　　　　if(r[j].key<r[k].key)
　　　　　　　　　k=j;
　　　　　　if (k!=i){//若k<>i，则交换，扩大有序区
　　　　　　　　r[0].key=r[i].key;
　　　　　　　　r[i].key=r[k].key;
　　　　　　　　r[k].key=r[0].key;
　　　　　　　}//end of if
　　　　　}//end of for
　　　}//end of selectsort

　quicksort(int low,int high)
　　{//对r[low..high]进行快速排序
　　　int pivotpos;
　　　if(low<high){
　　　　pivotpos=partition(low,high);//对r[low..high]进行一次快速排序，
            //以pivotpos为划分点，分成两个无序区r[low..pivotpos-1]和r[pivotpos+1..high]
        quicksort(low,pivotpos-1);//对r[low..pivotpos-1]进行快速排序
　　　  quicksort(pivotpos+1,high);//对r[pivotpos+1..high]进行快速排序
　　　 }//end of if
    }//end of quicksort