选择排序O(n^2)与快速排序O(nlogn)的优越性代码体现

随机函数生成一个超大数组：

【code】：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include<time.h>
 4 #include<stdlib.h>
 5 #include<dos.h>
 6 
 7 using namespace std;
 8 
 9 int main()
10 {
11     freopen("random.txt","w",stdout);
12     int n;
13     scanf("%d",&n);
14     int i;
15     srand(time(NULL));
16     printf("%d
",n);
17     for(i=0;i<n;i++)
18     {
19         printf("%d ",rand());
20     }
21     printf("
");
22     fclose(stdout);
23     return 0;
24 }
25 
26 
27 
28 /*
29     time_t sTime,fTime;
30     fTime=clock();
31     _sleep(1000);
32     sTime=clock(); //获取查找完成后的时间
33     double duration=(double)(sTime-fTime)/CLOCKS_PER_SEC; //计算查找用时
34     printf("此查询用时%lf秒

",duration);
35 
36 */

View Code

快速排序（文件输入输出）：
【code】：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<time.h>
 5 
 6 using namespace std;
 7 
 8 int partition(int *a,int left,int right)
 9 {
10     a[0] = a[left];  //设置a[left]为主键值，存于a[0]，即以a[left]值将[left,right]区间一分为二
11     while(left<right)
12     {
13         while(left<right&&a[right]>=a[0]) right--;  //从右边开始找到比主键值a[0]小的值，移到左边
14         a[left]=a[right];
15         while(left<right&&a[left]<=a[0]) left++;    //从左边开始找到比主键值a[0]大的值，移到右边
16         a[right]=a[left];
17     }
18     a[left] = a[0];  //跳出while循环后的left==right，此时，区间已经一分为二了，将a[left]的值还原
19     return left;
20 }
21 
22 void QuickSort(int *a,int left,int right)
23 {
24     if(left<right)  //快拍区间要大于1
25     {
26         int mid = partition(a,left,right);  //进行一次划分，以a[left]划分区间为左右两个区间
27         QuickSort(a,left,mid-1);   //对左区间进行进一步划分
28         QuickSort(a,mid+1,right);  //对左区间进行进一步划分
29     }
30 }
31 
32 int a[10000000];
33 
34 int main()
35 {
36     int n;
37 
38     freopen("random.txt","r",stdin);
39     freopen("quicksortout.txt","w",stdout);
40 
41     scanf("%d",&n);
42     int i;
43     for(i=1;i<=n;i++)
44     {
45         scanf("%d",a+i);
46     }
47 
48     time_t ftime,stime;
49     ftime = clock();  //获取排序前的时间
50 
51     QuickSort(a,1,n);
52 
53     stime = clock();  //获取排序后的时间
54     double duration=(double)(stime-ftime)/CLOCKS_PER_SEC; //计算排序用时
55 
56     for(i=1;i<=n;i++)
57     {
58         printf("%d ",a[i]);
59     }
60     putchar(10);
61 
62     freopen("CON","w",stdout);
63     printf("快速排序用时%lf
",duration);
64 
65     return 0;
66 }

View Code

选择排序：

【code】：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <time.h>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 void ChooseSort(int *a,int l,int r)
 9 {
10     int i,j;
11     for(i=l;i<=r;i++)
12     {
13         for(j=i+1;j<=r;j++)
14         {
15             if(a[i]>a[j])
16             {
17                 swap(a[i],a[j]);
18             }
19         }
20     }
21 }
22 
23 int a[10000000];
24 
25 int main()
26 {
27     int n;
28 
29     freopen("random.txt","r",stdin);
30     freopen("choosesortout.txt","w",stdout);
31 
32     scanf("%d",&n);
33     int i;
34     for(i=1;i<=n;i++)
35     {
36         scanf("%d",a+i);
37     }
38 
39     time_t ftime,stime;
40     ftime = clock();  //获取排序前的时间
41 
42     ChooseSort(a,1,n);
43 
44     stime = clock();  //获取排序后的时间
45     double duration=(double)(stime-ftime)/CLOCKS_PER_SEC; //计算排序用时
46 
47     for(i=1;i<=n;i++)
48     {
49         printf("%d ",a[i]);
50     }
51     putchar(10);
52     fclose(stdin);
53     fclose(stdout);
54 
55     freopen("CON","w",stdout);
56     printf("选择排序用时%lf
",duration);
57     fclose(stdout);
58 
59     return 0;
60 }

View Code

随机生成50000的随机数据
对比两种排序的时间优越性：

快速排序：

选择排序：