快速排序1亿个随机浮点数，居然用了400多秒。该怎么解决

快速排序1亿个随机浮点数，居然用了400多秒。。。
Intel(R) Core(TM)2 Duo CPU E7500 @2.93GHz

483秒

怎么来优化？

C/C++ code

#include<stdio.h>#include<stdlib.h>#include<time.h>#define MAX_NUMBER 100000000void create_random_numbers(float *numbers,int count){    srand((unsigned)time(NULL));    for(int i = 0; i < count;++i)    {        numbers[i] = (float)rand()/RAND_MAX*MAX_NUMBER;    }}void display_numbers(float *numbers,int count){    for(int i = 0; i < count; ++i)    {        if((i+1)%5 == 0)        {            putchar('\n');        }        printf("%.3f  ",numbers[i]);    }    putchar('\n');}void quicksort(float *numbers,int start,int end){    if(start >= end) return;    float key = numbers[start];    int i_start = start;    int i_end = end;    for(;;)    {        while(numbers[i_end] > key && i_start < i_end)        {            --i_end;        }        if(i_start >= i_end) break;        numbers[i_start++] = numbers[i_end];        while(numbers[i_start] <= key && i_start < i_end)        {            ++i_start;        }        if(i_start >= i_end) break;        numbers[i_end--] = numbers[i_start];    }    numbers[i_start] = key;    quicksort(numbers,start,i_start-1);    quicksort(numbers,i_start+1,end);}int main(void){    int NUM_COUNT=0;    time_t start_time,end_time;    printf("How many numbers do you want to sorting test: ");    scanf("%d",&NUM_COUNT);    float *numbers = (float*)malloc(sizeof(float)*NUM_COUNT);    create_random_numbers(numbers,NUM_COUNT);    puts("create random finished!");    printf("----------------------------------\n");    puts("sorting....");    time(&start_time);    quicksort(numbers,0,NUM_COUNT-1);    time(&end_time);    printf("used %d seconds!\n",end_time-start_time);    getchar();    puts("quick sort finished ,would you want to display the number?");    char choice = getchar();    if(choice == 'y')    {        display_numbers(numbers,NUM_COUNT);    }    free(numbers);    return 0;}

[解决办法]
如果有足够的内存，直接使用系统函数qsort排序就好了，

例子如下:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#define MAX_NUMBER 100000000
#define NUM_COUNT 100000

void create_random_numbers(float *numbers,int count)
{
float*p = numbers;
inti = 0;

srand((unsigned)time(NULL));

for(i = 0; i < count; i++)
{
// 不要用数组,指针快过数组
// numbers[i] = (float)rand()/RAND_MAX*MAX_NUMBER;
*p ++ = (float)rand()/RAND_MAX*MAX_NUMBER;
}
}

int CompareFloat(const void *s0, const void *s1)
{
float *f0, *f1;

f0 = (float *)s0;
f1 = (float *)s1;

/*
// 浮点数比较不能直接使用小于
*/
if( abs(*f0-*f1) < 0.000001 )
return 0;
else if( *f0 > *f1 )
return 1;
return -1;
}

void main()
{
float*numbers = NULL;
time_t start_time,end_time;
inti = 0;

numbers = (float*)malloc(sizeof(float)*NUM_COUNT);
time( &start_time );
create_random_numbers(numbers,NUM_COUNT);
time( &end_time );
printf("Create Time [%d]\n", end_time-start_time);
for( i = 0; i < 10; i ++ )
printf("[%d]=[%f]\n", i, numbers[ i ]);
time( &start_time );
qsort(numbers, NUM_COUNT, sizeof(float), CompareFloat);
time( &end_time );
printf("Sort Time [%d]\n", end_time-start_time);
for( i = 0; i < 10; i ++ )
printf("[%d]=[%f]\n", i, numbers[ i ]);

free( numbers );
}

查看更多 下一篇