该算法主要用来对给定数据集进行排序的,可以快速求出第N大的数字,时间为常数时间。
缺点:数据的范围不能太大。
步骤如下:
1. 给定一个待排序数组(相当于一群鸽子),创建一个备用数组(叫鸽巢数组)并初始化元素为0,备用数组的索引(鸽巢的编号)即是待排序数组的值(鸽子的重量)。
2. 把待排序数组的值(鸽子),放到数组(鸽巢)里(即用作备用数组的索引)。
3. 遍历鸽巢数组,最重的鸽巢编号排序为1,依次递增,得到每个鸽子的序号。
例如:
给定数字:1 1 5 3 9 6 0 5
1. 初始化自己创建的数组
0 1 2 3 4 5 6 7 8 9
2. 数组的里面存放的是该索引出现的次数
索引: 0 1 2 3 4 5 6 7 8 9
次数: 1 2 0 1 0 2 1 0 0 1
3.假设从9开始排名
第8 第6 第5 第3 第2 第1
出现次数为0的不需要参与排名