今天想在網上找一個實現好的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)排序算法——计数排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。