找阈值

3500个数字排序

结果

在我的电脑上找到了:10
跑了很多次都在10附近
本来想做个折线图,打开表格宕机了,先拿表格凑合

遇到的问题

运行程序慢
效率提高不明显
结果和正确答案有出入
10000万溢出了
100万以上没有溢出的时候都是段错误
我也不知道为什么

修改了main,不用一直改数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main(){
int array[M];
for(int j=50;j>0;j--){
printf("%d:\n",j);
for(int i=0;i<5;i++){
double duration;
create_Ary(array,M);
clock_t start, finish;
start = clock();
quicksort(array,0,M,j);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
//print(array,M);
printf( "%f seconds\n", duration );
//elapsed_time();

}
}
return 0;
}

下面是原程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define M 5000//调整这个改变排序的数的个数
void SelectionSort(int a[],int p,int r);//选择排序
void create_Ary (int a[], int n);//制造随机数组
int partition(int array[],int p,int r);//将数组分成大于某个数和小于某个数两部分
void exchange(int *p,int *q);//交换函数
void print(int array[],int len);//打印数组元素
void quicksort(int array[],int p,int r);//快速排序
int main(){
int array[M];
double duration;
create_Ary(array,M);
clock_t start, finish;
start = clock();
quicksort(array,0,M);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
//print(array,M);
printf( "%f seconds\n", duration );
//elapsed_time();
return 0;
}
void quicksort(int array[],int p,int r){
int q=0;
if(r-p<20){
SelectionSort(array,p,r);
}
else{
if(p<r){
q=partition(array,p,r);
quicksort(array,p,q);
quicksort(array,q+1,r);
}
}
}
int partition(int array[],int p,int r){
int x=array[r-1];
int i=p-1;
for(int j=p;j<r-1;j++){//最后一个数内定了
if(array[j]<=x){
exchange(&array[i+1],&array[j]);
i+=1;
}
}
exchange(&array[i+1],&array[r-1]);
i++;
return i;
}
void exchange(int *p,int *q){
int t=*p;
*p=*q;
*q=t;
return;
}
void print(int array[],int len){
for(int i=0;i<len;i++){
printf("%d ",array[i]);
}
return;
}
void elapsed_time(){
printf("Elapsed time:%lu secs.\n",clock()/CLOCKS_PER_SEC);
}
void create_Ary (int a[], int n)
{
srand(time(0)); //使随机数函数 rand 产生一序列随机数而设置种子值
int i,j,x;
i = 0;
while (i<n)
{
x=rand( );
if (x>=10000) //产生两位在 10≤而<100 范围内的数
continue;
j=0;
while (j<=i&&a[j]!=x) //舍弃相同元素
j++;
if (j>i)a[i++]=x; //不同的元素送入数组
}
}
void SelectionSort(int a[],int p,int r){
int i,j;
for(i = p ; i < r-1 ; i++){
int min_index = i;
for(j = i + 1 ; j < r; j++)
if(a[ min_index ] > a[j])
min_index = j;
if(min_index != i){
int temp = a[i];
a[i] = a[min_index];
a[min_index] = temp;
}
}
}