现在的位置: 首页 > 综合 > 正文

计数排序

2014年03月20日 ⁄ 综合 ⁄ 共 2349字 ⁄ 字号 小 中 大 ⁄ 评论关闭
  1. /*
  2.  * 算法名称：计数排序
  3.  * 算法思想：在最后排好序的序列中，第j个键码恰恰大于(j-1)个其它键码.
  4.  *           比如:如果知道某个键码确实超过7个其它键码,而且没有两个键
  5.  *           码相同,刚在排序之后对应的记录应当进入位置8.
  6.  * 算法实现:
  7.  *           通过维护一张辅助表count[1]...count[N],对于小于一个给定键
  8.  *           码的键码个数进行计数,实现用键码K1,...Kn对记录R1,...,Rn排
  9.  *           序. 算法结束时,count[j]+1确定记录Rj的最后位置.
  10.  */
  12. #include <stdio.h>
  13. #include <time.h>
  14. #include <stdlib.h>     /* for rand() and srand() */
  16. #define N 10            /* the number of elements */
  18. //@param: 
  19. //array: to be sorted array.
  20. int *count_sort(int *array);
  22. //function:
  23. //          initial the array with integer.
  24. //@param:
  25. //array: to be sorted array.
  26. void init_rand(int *array);
  28. //function: print the elements of the array.
  29. //@param:
  30. //array: to be sorted array.
  31. void print_array(int *array);
  32. int main(void)
  33. {
  34.   int array[N];
  36.   init_rand(array);
  37.   printf("The array has been initialed as follows:/n");
  38.   print_array(array);
  40.   count_sort(array);
  41.   printf("After count sort:/n");
  42.   print_array(array);
  44.   return 0;
  46. }//main()
  48. void init_rand(int *array)
  49. {
  50.   int i;
  51.   srand((unsigned)time(NULL));
  53.   for (i = 0; i < N; i++)
  54.   {
  55.     array[i] = rand() % 900 + 100;     /* initialize the array between 100 and 999 */
  56.   }//for
  58. }//init_rand()
  60. void print_array(int *array)
  61. {
  62.   int i;
  63.   for (i = 0; i < N; i++)
  64.   {
  65.     printf("%d/t", array[i]);
  66.   }//for
  67.   printf("/n");
  68. }//print_array()
  70. int *count_sort(int *array)
  71. {
  72.   int i,j;
  73.   int count[N] = {0};
  74.   int temp[N] = {0};
  76.   for (i = 1; i < N; i++)
  77.   {
  78.     for (j = 0; j < i; j++)
  79.     {
  80.       array[i] < array[j] ? count[j]++ : count[i]++;
  81.     }//for
  82.   }//for
  84.   printf("Now, the elements' value of count are as follows:/n");
  85.   print_array(count);
  87.   for (i = 0; i < N; i++)
  88.   {
  89.     temp[i] = array[i];
  90.   }//for
  91.   
  92.   for (i = 0; i < N; i++)
  93.   {
  94.     array[count[i]] = temp[i];
  95.   }//for
  96.   return array;
  97. }//count_sort()
  98. //运行情况;
    1. lee@Lee:~/MyProject/sort/count_sort$ ./count_sort 
    2. The array has been initialed as follows:
    3. 418 292 332 357 709 779 336 103 503 802 
    4. Now, the elements' value of count are as follows:
    5. 5   1   2   4   7   8   3   0   6   9   
    6. After count sort:
    7. 103 292 332 336 357 418 503 709 779 802 
    8. --------------------------------------------------------------------
    9. lee@Lee:~/MyProject/sort/count_sort$ ./count_sort 
    10. The array has been initialed as follows:
    11. 486 158 181 688 235 687 566 420 185 747 
    12. Now, the elements' value of count are as follows:
    13. 5   0   1   8   3   7   6   4   2   9   
    14. After count sort:
    15. 158 181 185 235 420 486 566 687 688 747 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞