经典排序算法 - Flash Sort
经典排序算法 - Flash Sort FlashSort依然类似桶排,主要改进了对要使用的桶的预测,或者说,减少了无用桶的数量从而节省了空间,例如 待排数字[ 6 2 4 1 5 9 100 ]桶排需要100个桶,而flash sort则由于可以预测桶则只需要7个桶 即待排数组长度个桶,如何预测将要使用的桶有这么一个公式 该排序有前置条件,需要知道待排数组的区间和待排数组的长度, 例如已知待排数组[ 6 2 4 1 5 9 ]的长度为6,最大值9,最小值1,这三个是已知条件,如果无法知道这三个则无法应用该排序 ? 预测的思想 如果有这样一个待排数组,其最大值是100,最小值是1,数组长度为100,那么50在排完序后极有可能出现在正中间,flash sort就是基于这个思路 ? 预测桶号细节 待排数组[ 6 2 4 1 5 9 ] 具体看6可能出现的桶号 Ai - Amin 是 6 - 1 = 5 Amax - Amin 是9 - 1 = 8 m - 1 是数组长度6 - 1 = 5 则(m - 1) * (Ai - Amin) / (Amax - Amin) = 5 * 5 / 8 =25/8 = 3.125 最后加上1等于 4.125 6预测的桶号为4.125 2预测的桶号为1.625 4预测的桶号为2.875 1预测的桶号为1 5预测的桶号为3.5 9预测的桶号为5 去掉小数位后,每个数字都拥有自己预测的桶号,对应如下所示 待排数组[ 6 2 4 1 5 9 ] 预测桶号[ 4 1 2 1 3 5 ] ? 入桶规则 1号桶 2,1 2号桶 4 3号桶 5 4号桶 6 5号桶 9 1号桶内两个数字使用任意排序算法使之有序,其它桶如果此种情况同样需要在桶内排序,使用什么排序算法不重要,重要的是排成从小到大即可 最后顺序从桶里取出来即可 [1 2 4 5 6 9] 参考http://en.wikipedia.org/wiki/Flashsort (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |