1 /* 2 请设计直接插入排序算法函数void insertSort(int a[],int n)，对a[1]..a[n]进行升序排序。 3 并测试在不同数据规模下的排序效率。 4 */ 5 #include "Arrayio.h" 6 #define N 10000     /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/ 7  8 /*请将本函数补充完整，并进行测试*/ 9 void insertSort(int a[],int n)10 {11     /*直接插入排序*/12     int i;13     for(i=2; i<=n; i++)14     {15         if(a[i]<a[i-1])16         {17             int j = i-1;18             int tmp = a[i];19             while(tmp<a[j])20             {21                 a[j+1] = a[j];22                 j--;23             }24             a[j+1] = tmp;25         }26     }27 }28 29 int  main()30 {31     int a[N+1],n;                     /*数据存储在a[1]...a[N]中*/32     printf("数据初始化...\n");33     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/34     printf("%d个数据排序中...\n",n);35     insertSort(a,n);36     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/37     printf("排序结束，排序结果保存在out.txt文件中。\n");38     return 0;39 }

 1 /* 2 请设计二分插入排序算法函数void binInsertSort(int a[],int n)，对a[1]..a[n]进行升序排序。 3 并测试在不同数据规模下的排序效率。 4 */ 5 #include "Arrayio.h" 6 #define N 10000     /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/ 7 #include <algorithm> 8  9 using namespace std;10 11 12 /*请将本函数补充完整，并进行测试*/13 void insertSort(int a[],int n)14 {15     /*直接插入排序*/16     for(int i=2; i<=n; i++)17     {18         if(a[i]<a[i-1])19         {20             int j = i-1;21             int tmp = a[i];22             while(tmp<a[j])23             {24                 a[j+1] = a[j];25                 j--;26             }27             a[j+1] = tmp;28         }29     }30 }31 32 void binInsertSort(int a[],int n)33 {34     for(int i=2;i<=n;i++) {35         if(a[i]<a[i-1]) {36             int pos = lower_bound(a+1,a+i,a[i]) - a;37             for(int j=i-1;j<=pos+1;j--)38                 a[j+1] = a[j];39             a[pos+1] = a[i];40         }41     }42 }43 44 int  main()45 {46     int a[N+1],n;                     /*数据存储在a[1]...a[N]中*/47     printf("数据初始化...\n");48     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/49     printf("%d个数据排序中...\n",n);50     insertSort(a,n);51     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/52     printf("排序结束，排序结果保存在out.txt文件中。\n");53     return 0;54 }

 1 /* 2 请设计shell排序算法函数void shellSort(int a[],int n)，对a[1]..a[n]进行升序排序。 3 并测试在不同数据规模下的排序效率。 4 */ 5 #include "Arrayio.h" 6 #define N 10000     /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/ 7  8 /*请将本函数补充完整，并进行测试*/ 9 void shellSort(int a[],int n)10 {11     for(int d=n/2;d>=1;d=d/2)12     {13         for(int i=d+1;i<=n;i++) {14             int tmp = a[i];15             int j;16             for(j=i-d;j>0&&tmp<a[j];j=j-d) {17                 a[j+d] = a[j];18             }19             a[j+d] = tmp;20         }21     }22 23 }24 25 int  main()26 {27     int a[N+1],n;                     /*数据存储在a[1]...a[N]中*/28     printf("数据初始化...\n");29     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/30     printf("%d个数据排序中...\n",n);31     shellSort(a,n);32     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/33     printf("排序结束，排序结果保存在out.txt文件中。\n");34     return 0;35 }

 1 /* 2 请设计简单选择排序算法函数void selectSort(int a[],int n)，对a[1]..a[n]进行升序排序。 3 并测试在不同数据规模下的排序效率。 4 */ 5 #include "Arrayio.h" 6 #define N 10000     /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/ 7 #include <algorithm> 8  9 using namespace std;10 11 /*请将本函数补充完整，并进行测试*/12 void selectSort(int a[],int n)13 {14     for(int i=1;i<n;i++) {15         int k = i;16         for(int j=i+1;j<=n;j++) {17             if(a[j]<a[k])18                 k = j;19         }20         if(k!=i)21         {22             swap(a[i],a[k]);23         }24     }25 }26 27 int  main()28 {29     int a[N+1],n;                     /*数据存储在a[1]...a[N]中*/30     printf("数据初始化...\n");31     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/32     printf("%d个数据排序中...\n",n);33     selectSort(a,n);34     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/35     printf("排序结束，排序结果保存在out.txt文件中。\n");36     return 0;37 }

 1 /* 2 请设计筛选函数void sift(int a[],int k,int n)，对a[k] 进行筛选， 3 并利用其设计堆排序算法函数void heapSort(int a[],int n)， 4 对a[1]..a[n]进行升序排序。并测试在不同数据规模下的排序效率。（详见lab10_05.c） 5 */ 6 #include "Arrayio.h" 7 #define N 10000     /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/ 8  9 /*请将本函数补充完整，并进行测试*/10 void sift(int a[],int k,int n)11 {12     int i,j,finished;13     i=k;14     j=2*i;15     a[0]=a[k];16     finished=0;17     while((j<=n)&&(!finished))18     {19         if((j<n)&&(a[j+1]>a[j]))20             j++;21         if(a[0]>=a[j])22             finished=1;23         else24         {25             a[i]=a[j];26             i=j;27             j=2*j;28         }29     }30     a[i]=a[0];31 }32 33 void heapSort(int a[],int n)34 {35     int i;36     for (i=n/2; i>=1; i--)37         sift(a,i,n);38     for (i=n; i>1; i--)39     {40         a[0]=a[i];41         a[i]=a[1];42         a[1]=a[0];43         sift(a,1,i-1);44     }45 }46 47 int  main()48 {49     int a[N+1],n;                     /*数据存储在a[1]...a[N]中*/50     printf("数据初始化...\n");51     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/52     printf("%d个数据排序中...\n",n);53     heapSort(a,n);54     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/55     printf("排序结束，排序结果保存在out.txt文件中。\n");56     return 0;57 }

 1 /* 2 请设计冒泡排序算法函数void bubbleSort(int a[],int n)，对a[1]..a[n]进行升序排序。 3 并测试在不同数据规模下的排序效率。 4 */ 5 #include "Arrayio.h" 6 #define N 10000     /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/ 7 #include <algorithm> 8  9 using namespace std;10 11 /*请将本函数补充完整，并进行测试*/12 void bubbleSort(int a[],int n)13 {14     for(int i=1;i<=n-1;i++) {15         bool flag = true;16         for(int j=1;j<=n-i;j++) {17             if(a[j]>a[j+1]) {18                 swap(a[j],a[j+1]);19                 flag = false;20             }21         }22         if(flag) return ;23     }24 }25 26 int  main()27 {28     int a[N+1],n;                     /*数据存储在a[1]...a[N]中*/29     printf("数据初始化...\n");30     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/31     printf("%d个数据排序中...\n",n);32     bubbleSort(a,n);33     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/34     printf("排序结束，排序结果保存在out.txt文件中。\n");35     return 0;36 }

 1 /* 2 请设计快速排序算法函数void quickSort(int a[],int low,int right)，对a[low]..a[right]进行升序排序。 3 并测试在不同数据规模下的排序效率。 4 */ 5 #include "Arrayio.h" 6 #define N 10000     /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/ 7  8 /*请将本函数补充完整，并进行测试*/ 9 void quickSort(int a[],int low,int right )10 {11     int i = low, j = right;12     int tmp = a[low];13     if(low<right)14     {15         while(i<j)16         {17             while(i<j&&a[j]>=tmp)18                 j--;19 20             if(i<j)21             {22                 a[i] = a[j];23                 i++;24             }25 26             while(i<j&&a[i]<=tmp)27                 i++;28 29             if(i<j)30             {31                 a[j] = a[i];32                 j--;33             }34         }35         a[i] = tmp;36         quickSort(a,low,j-1);37         quickSort(a,j+1,right);38     }39 }40 41 int  main()42 {43     int a[N+1],n;                     /*数据存储在a[1]...a[N]中*/44     printf("数据初始化...\n");45     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/46     printf("%d个数据排序中...\n",n);47     quickSort(a,1,n);48     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/49     printf("排序结束，排序结果保存在out.txt文件中。\n");50     return 0;51 }