经典排序算法 - 鸽巢排序Pigeonhole sort

来源:互联网 时间:1970-01-01

经典排序算法 - 鸽巢排序Pigeonhole sort

原理类似桶排序,同样需要一个很大的鸽巢[桶排序里管这个叫桶,名字无所谓了]

鸽巢其实就是数组啦,数组的索引位置就表示值,该索引位置的值表示出现次数,如果全部为1次或0次那就是桶排序

例如

var pigeonHole = new int[100];

pigeonHole[0]的值表示0的出现次数...

pigeonHole[1]的值表示1的出现次数...

pigeonHole[2]的值表示2的出现次数...

参考 http://hi.baidu.com/wangxvfeng101/blog/item/a2c22560e57260c58cb10d8c.html

代码仅供参考,欢迎谌误

/// 鸽巢排序 /// </summary> /// <param name="unsorted">待排数组</param> /// <param name="maxNumber">待排数组中的最大数,如果可以指定的话</param> /// <returns></returns> static int[] pogeon_sort(int[] unsorted, int maxNumber = 10) { int[] pogeonHole = new int[maxNumber + 1]; foreach (var item in unsorted) { pogeonHole[item]++; } return pogeonHole; /* * pogeonHole[10] = 4; 的含意是 * 在待排数组中有4个10出现,同理其它 */ } static void Main(string[] args) { int[] x = { 99, 65, 24, 47, 47, 50, 99, 88, 66, 33, 66, 67, 31, 18, 24 }; var sorted = pogeon_sort(x, 99); for (int i = 0; i < sorted.Length; i++) { for (int j = 0; j < sorted[i]; j++) { Console.WriteLine(i); } } Console.ReadLine(); }

相关阅读:
Top