C#桶排序

2016-12-03  本文已影响0人  本来想取long但是有人用了

桶排序不愧为比快排还要快的排序方法(一定的意义上)

桶排序:

首先定义一个大容量的整型数组例如int[] intArray={1,5,483,89,3,489,5,.....};

数组种有多个元素,首先获取最大值则可以列一个数组int intNewArray=[max];

可以看做为0到max长度值全为0的数组

{0,1,2,3,4,5,6,7,8.....,max};

一个从最小值到最大值的数组然后做一次循环使intArray的值达到对应的位置入1到入intNewArray{0,1,0,0,0,0,0,,0,0};

则使intArray的值全都到入intNewArray上,然后遍历输出intNewArray的值为0可以跳过,若原数组有0可以进行判断

无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9](考试分数为1-100等)

例如待排数字[6 2 4 1 5 9]

准备10个空桶,最大数个空桶

[6 2 4 1 5 9]           待排数组

[0 0 0 0 0 0 0 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

1,顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]

[62 4 1 5 9]           待排数组

[0 0 0 0 0 010 0 0]   空桶

[0 1 2 3 4 567 8 9]   桶编号(实际不存在)

2,顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶

[6 24 1 5 9]           待排数组

[0 010 0 0 1 0 0 0]   空桶

[0 123 4 5 6 7 8 9]   桶编号(实际不存在)

3,4,5,6省略,过程一样,全部入桶后变成下边这样

[6 2 41 5 9]           待排数组

[011 0 11 1 0 0 1]   空桶

[01 2345 6 7 89]   桶编号(实际不存在)

可能这只是浅的理解 有错误请指出

部分转载http://www.cnblogs.com/kkun/archive/2011/11/23/2260267.html

上一篇 下一篇

猜你喜欢

热点阅读