找阈值

T

3500个数字排序

结果

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

遇到的问题

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

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

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;
}

下面是原程序

#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;
        }
    }
}