O(n) - Bucket Sort
2018-03-31 本文已影响0人
Super_Alan
Bucket Sort
Runtime O(n); Space O(n); // n 为 array items value range.
适合数据密度大的array 排序，例如电话号码。
Bucket Sort 弊端：
- Need to know how to handle duplicates:
- Array of LinkedList
- Array of Integer counter
- Need to know the max value in the unsorted array
- Need to make sure of enough memory
以 Penn State 电话号码为例，首三位412，可以使用 Integer 来表示后七位。Java 中，Integer 最大值为 2^31 - 1, 值为2.147483647 * 10^9。
一个int为32bit，4 Bytes. An integer array with size 10^7 需要 40MB memory。
4 Byte * 10^7 => 40 MB
