最快的排序算法:   桶 排 序                         
 经分析通过比较的排序算法如,选择排序,插入排序,快速排序,堆排序
 等最快为 n*log(n),这是比较排序算法的极限任何通过比较进行排序
 的算法都不可能超过这个极限. 现在要介绍的 桶排序 可以超过它为
 n ,当然 桶排序 的灵活性却拿不出手,必须要知道待排序数组中最大
 的数.下面的程序,首先由用户输入数组的大小,程序随机产生最大数为
 不超过 10000 的随机数组,最后输出原始数组,以及排序后的数组.  

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

#include <stdio.h>
#include <malloc.h>
#include <memory.h>
#include <stdlib.h>
#include <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 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("\n\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("\n\nContinue(y/n)? :");
  getchar();
  i = getchar();
  if(isupper(i))
   i = tolower(i);
  if(i == 'n')
   break;
 }
 return 0;
}

评论