hash sorting hash 排序

raymond1984

                偶尔看到了关于hash sorting算法的讨论，顺便查找了一下
http://arxiv.org/abs/cs.DS/0408040
优点：
1. Linear time complexity, even in the worst case; for the in-situ proportional to the data structure size, and for the direct proportional to the data list size.
2. The hash sort puts data elements in the correct position, does not move them afterward – data quiesence
3. Data independence – data elements in the data set are mapped by their unique value, and do not depend on the predecessor or successor in the data set
4. High speed lookup is possible once the data is sorted – faster than binary search; or alternatively, to the approximate location within the data structure.
劣势：
1. Sparsity of data values in range – wasteful of space
2. Multi-dimensional data structure is required – square planar matrices are inconsistent with underlying linear memory in one-dimension
3. Works only with numeric values, requires conversion for non-numeric value
4. The data range of values must be known for the algorithm to work effectively
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/94300/showart_1904877.html