排序——数据结构课程作业

(╥╯^╰╥)

 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("数据初始化...
");
33     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
34     printf("%d个数据排序中...
",n);
35     insertSort(a,n);
36     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/
37     printf("排序结束，排序结果保存在out.txt文件中。
");
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("数据初始化...
");
48     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
49     printf("%d个数据排序中...
",n);
50     insertSort(a,n);
51     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/
52     printf("排序结束，排序结果保存在out.txt文件中。
");
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("数据初始化...
");
29     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
30     printf("%d个数据排序中...
",n);
31     shellSort(a,n);
32     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/
33     printf("排序结束，排序结果保存在out.txt文件中。
");
34     return 0;
35 }

shell排序算法

 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("数据初始化...
");
31     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
32     printf("%d个数据排序中...
",n);
33     selectSort(a,n);
34     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/
35     printf("排序结束，排序结果保存在out.txt文件中。
");
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         else
24         {
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("数据初始化...
");
51     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
52     printf("%d个数据排序中...
",n);
53     heapSort(a,n);
54     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/
55     printf("排序结束，排序结果保存在out.txt文件中。
");
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("数据初始化...
");
30     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
31     printf("%d个数据排序中...
",n);
32     bubbleSort(a,n);
33     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/
34     printf("排序结束，排序结果保存在out.txt文件中。
");
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("数据初始化...
");
45     n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
46     printf("%d个数据排序中...
",n);
47     quickSort(a,1,n);
48     saveData(a,n,"out.txt");          /*排序结果存放在out.txt文件中*/
49     printf("排序结束，排序结果保存在out.txt文件中。
");
50     return 0;
51 }

快速排序算法