【vlfeat】O(n)排序算法——计数排序

今天想在网上找一个实现好的er算法来着，没啥具体的资料，无奈只能看vlfeat的mser源码，看能不能修修补补实现个er。

于是，看到某一段感觉很神奇，于是放下写代码，跑来写博客，也就是这段

1 /* ----------------------------------------------------------------- 2 * Sort pixels by intensity 3 * -------------------------------------------------------------- */ 4 5 { 6 vl_uint buckets [ VL_MSER_PIX_MAXVAL ] ; 7 8 /* clear buckets */ 9 memset (buckets, 0, sizeof(vl_uint) * VL_MSER_PIX_MAXVAL ) ; 10 11 /* compute bucket size (how many pixels for each intensity 12 value) */ 13 for(i = 0 ; i < (int) nel ; ++i) { 14 vl_mser_pix v = im [i] ; 15 ++ buckets [v] ; 16 } 17 18 /* cumulatively add bucket sizes */ 19 for(i = 1 ; i < VL_MSER_PIX_MAXVAL ; ++i) { 20 buckets [i] += buckets [i-1] ; 21 } 22 23 /* empty buckets computing pixel ordering */ 24 for(i = nel ; i >= 1 ; ) { 25 vl_mser_pix v = im [ --i ] ; 26 vl_uint j = -- buckets [v] ; 27 perm [j] = i ; 28 } 29 }

我看注释说排序，我觉得这个为啥连排序也要自己造轮子，为啥不直接用个快排啥的，后来仔细看了下代码，才发现不然，复杂度竟然是O(n)。

这段代码的目的原本是为了把一幅图像中的像素灰度值按升序排列，这里巧妙利用像素值取值是在0-255内这个特点，专门开辟了一个256长度的数组，记录每个灰度值的像素的个数，也就是这段：

1 /* compute bucket size (how many pixels for each intensity 2 value) */ 3 for(i = 0 ; i < (int) nel ; ++i) { 4 vl_mser_pix v = im [i] ; 5 ++ buckets [v] ; 6 }

之后把这个统计值转换成比改灰度值小的像素的个数：

1 /* cumulatively add bucket sizes */ 2 for(i = 1 ; i < VL_MSER_PIX_MAXVAL ; ++i) { 3 buckets [i] += buckets [i-1] ; 4 }

比像素m小的像素有buckets[m]个，那么m就排在buckets[m-1]到buckets[m]之间。每出现一个m，buckets[m]就--，m就排在buckets[m]处。

1 /* empty buckets computing pixel ordering */ 2 for(i = nel ; i >= 1 ; ) { 3 vl_mser_pix v = im [ --i ] ; 4 vl_uint j = -- buckets [v] ; 5 perm [j] = i ; 6 }

后来百度发现这个叫做计数排序。这种排序并不需要比较，O(n+k)时间内可以完成。n是数组的个数，k是数组的取值范围。一般来说，这种算法只适合K比较小的情况。

 

转载于:https://www.cnblogs.com/jugg1024/p/4798731.html

总结

以上是生活随笔为你收集整理的【vlfeat】O(n)排序算法——计数排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。