桶排序 bucket sort

https://github.com/hotwater99/practice_datastructure_and_algorithm.git

《数据结构与算法分析——C语言描述》机械工业出版社，原书第2版，7.6

桶排序的时间复杂度为O(N+K)，但是需要满足前提条件：待排序的元素必须为小于M的正整数或者是0（负的整数也可以，就需要再多处理一下）。

待排序的数组array[N]，另外使用一个大小为M+1的数组tmp_array[]，把这个数组当成是M+1个桶，全部初始化为0，桶tmp_array[x]用来存放array[]中值未x的元素的个数。

依次扫描array[]中的元素，如果array[k]=x，那么桶tmp_array[x]就+1，把它们都记录到桶中。最后依次打印出桶tmp_array[]就完成了排序。

桶排序：

  1 void BucketSort(ElementType array[], int N)
  2 {
  3   int i, pos, bucket_size = MAX_ELMENT + 1;
  4   ElementType *tmp_array;
  5 
  6   tmp_array = (ElementType *)malloc(bucket_size * sizeof(ElementType));
  7   memset(tmp_array, 0, bucket_size * sizeof(ElementType));
  8 
  9   if (tmp_array != NULL) {
 10     for (i = 0; i < N; i++) {
 11       tmp_array[array[i]]++;
 12     }
 13 
 14     pos = 0;
 15     for (i = 0; i < bucket_size; i++) {
 16       while(tmp_array[i]-- > 0) {
 17         array[pos++] = i;
 18       }
 19     }
 20     free(tmp_array);
 21   }
 22   else {
 23     // error
 24   }
 25 }

完整代码：

  1 #include <iostream>
  2 #include <ctime>
  3 #include <string.h>
  4 
  5 using namespace std;
  6 
  7 typedef unsigned int     ElementType;
  8 
  9 #define random(x)       (rand() % x)
 10 #define ARRAY_LENTH     10
 11 #define MAX_ELMENT      (ARRAY_LENTH + ARRAY_LENTH)
 12 
 13 void BucketSort(ElementType array[], int N)
 14 {
 15   int i, pos, bucket_size = MAX_ELMENT + 1;
 16   ElementType *tmp_array;
 17 
 18   tmp_array = (ElementType *)malloc(bucket_size * sizeof(ElementType));
 19   memset(tmp_array, 0, bucket_size * sizeof(ElementType));
 20 
 21   if (tmp_array != NULL) {
 22     for (i = 0; i < N; i++) {
 23       tmp_array[array[i]]++;
 24     }
 25 
 26     pos = 0;
 27     for (i = 0; i < bucket_size; i++) {
 28       while(tmp_array[i]-- > 0) {
 29         array[pos++] = i;
 30       }
 31     }
 32     free(tmp_array);
 33   }
 34   else {
 35     // error
 36   }
 37 }
 38 
 39 int main() {
 40   ElementType test_array[ARRAY_LENTH];
 41   int i, N = ARRAY_LENTH;
 42 
 43   clock_t start_time, stop_time;
 44 
 45   for (i = 0; i < N; i++) {
 46     test_array[i] = random(MAX_ELMENT);
 47   }
 48 
 49   if (N <= 100) {
 50     cout << "raw : ";
 51     for (i = 0; i < N; i++) {
 52       cout << test_array[i] << " ";
 53     }
 54     cout << endl;
 55   }
 56 
 57   start_time = clock();
 58 
 59   BucketSort(test_array, N);
 60 
 61   stop_time = clock();
 62 
 63   if (N <= 100) {
 64     cout << "sort: ";
 65     for (i = 0; i < N; i++) {
 66       cout << test_array[i] << " ";
 67     }
 68     cout << endl;
 69   }
 70 
 71   cout << "BucketSort(" << N << ")..." << endl;
 72   cout << "total time used: ";
 73   cout << (double)(stop_time - start_time) / CLOCKS_PER_SEC << "s" << endl;
 74 
 75   system("pause");
 76 
 77   return 0;
 78 }

测试结果

N=10，MAX_ELMENT=2*N

raw : 1 7 14 0 9 4 18 18 2 4
sort: 0 1 2 4 4 7 9 14 18 18
BucketSort(10)...
total time used: 0s

N=100，MAX_ELMENT=2*N

raw : 41 67 134 100 169 124 78 158 162 64 105 145 81 27 161 91 195 142 27 36 191 4 102 153 92 182 21 116 118 95 47 126 171 138 69 112 67 99 35 94 103 11 122 133 73 64 141 111 53 68 147 44 62 157 37 59 123 141 129 178 116 35 190 42 88 106 40 142 64 48 46 5 90 129 170 150 6 101 193 148 29 23 84 154 156 40 166 176 131 108 144 39 26 123 137 138 118 82 129 141
sort: 4 5 6 11 21 23 26 27 27 29 35 35 36 37 39 40 40 41 42 44 46 47 48 53 59 62 64 64 64 67 67 68 69 73 78 81 82 84 88 90 91 92 94 95 99 100 101 102 103 105 106 108 111 112 116 116 118 118 122 123 123 124 126 129 129 129 131 133 134 137 138 138 141 141 141 142 142 144 145 147 148 150 153 154 156 157 158 161 162 166 169 170 171 176 178 182 190 191 193 195
BucketSort(100)...
total time used: 0s

N=1000，MAX_ELMENT=2*N

BucketSort(1000)...
total time used: 0s

N=10000，MAX_ELMENT=2*N

BucketSort(10000)...
total time used: 0s

N=100000，MAX_ELMENT=2*N

BucketSort(100000)...
total time used: 0.002s

N=100000，MAX_ELMENT=10*N

BucketSort(100000)...
total time used: 0.004s