桶排序

一、什么是桶排序二、桶排序的实现三、复杂度分析四、应用

一、什么是桶排序

桶排序（Bucket Sort）：如果待排序的数字是有范围整数，可以用数组下标与数值一一对应的方法存入数组中，然后按照数组下标输出数据，得到结果就是有序序列。

二、桶排序的实现

int main() { int i = 0; const int n = 10; int arr[n] = {9, 0, 8, 1, 7, 2, 6, 3, 5, 8}; int a[n + 1] = {0}; for (i = 0; i < n; i ++) { a[arr[i]] ++; } for (i = 0; i < n; i ++) { cout << a[i] << " "; } cout << endl; return 0; }

三、复杂度分析

n为元素的个数，m为桶的个数。如果算上输出的话，桶排序的时间复杂读是O(n + m)，这是非常快的排序。但是有时候对空间的消耗太大了，比如待排序的元素，跨度很大如：1、1000、100000，太浪费空间，这种情况下不适合桶排序。

四、应用

可以用桶排序完成去重与计数。 去重：将数据装进桶中后，然后按照arr[i] > 0，来完成去重。 计数：桶中的数据就是该元素出现的次数。