最快的排序算法_桶排序

最快的排序算法 

[ 江南孤峰 发表于 2006-11-9 12:57:00 ] 

  

/****************************************************************\

 最快的排序算法:   桶 排 序                          

 经分析通过比较的排序算法如,选择排序,插入排序,快速排序,堆排序 

 等最快为 n*log(n),这是比较排序算法的极限任何通过比较进行排序 

 的算法都不可能超过这个极限. 现在要介绍的 桶排序 可以超过它为 

 n ,当然 桶排序 的灵活性却拿不出手,必须要知道待排序数组中最大 

 的数.下面的程序,首先由用户输入数组的大小,程序随机产生最大数为

 不超过 10000 的随机数组,最后输出原始数组,以及排序后的数组.   

      #########################################

         独学而无友，则孤陋而寡闻  

         诚交天下程序员  !  

         Q 群： 28011342  

      #########################################

                                                             

 编译器: VC ++ 6.0  Author : 江南孤峰   Time :2006–10–27 

\****************************************************************/ 

＃i nclude <stdio.h>

＃i nclude <malloc.h>

＃i nclude <memory.h>

＃i nclude <stdlib.h>

＃i nclude <ctype.h>

int main(){

 int order[10000],total,*array,i;

 while( 1){

  memset(order,0,sizeof(int)*10000);

  printf("\nPlease input the size of the source array:");

  scanf("%d",&total);

  array = (int *)malloc(sizeof(int)*total + 4);

  printf("The source array as follow:\n");

  for(i = 0; i < total; i ++){

   array[i] = rand() % 10000;

   printf("%d ",array[i]);

   order[array[i]] ++; // 这里就是排序,够简洁吧 !

  }

  printf("\nThe array after by order as follow:\n");

  for(i = 0; i < 10000; i ++){

   while(order[i]){

    printf("%d ",i);

    order[i] –;

   }

  }

  free(array);

  printf("\nContinue(y/n)? :");

  getchar();

  i = getchar();

  if(isupper(i))

   i = tolower(i);

  if(i == 'n')

   break;

 }

 return 0;

}