女人自慰AV免费观看内涵网,日韩国产剧情在线观看网址,神马电影网特片网,最新一级电影欧美,在线观看亚洲欧美日韩,黄色视频在线播放免费观看,ABO涨奶期羡澄,第一导航fulione,美女主播操b

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

深入淺談計數排序

算法與數據結構 ? 來源:袁廚的算法小屋 ? 作者:廚子 ? 2021-04-28 16:20 ? 次閱讀

計數排序雖然不是面試??碱}目,但是計數排序的求統計數組步驟和最后元素歸位思想是我們刷題時經常用到的,例如原地置換,使用數組模擬 hashmap 等,所以還是很有必要看一下的。

今天我們就一起來看看線性排序里的計數排序到底是怎么回事吧。

我們將鏡頭切到袁記菜館

因為今年袁記菜館的效益不錯,所以袁廚就想給員工發些小福利,讓小二根據員工工齡進行排序,但是菜館共有 100000 名員工,菜館開業 10 年,員工工齡從 0 - 10 不等。

看來這真是一個艱巨的任務啊。

當然我們可以借助之前說過的 歸并排序 和 快速排序 解決,但是我們有沒有其他更好的方法呢?

了解排序算法的老哥可能已經猜到今天寫什么啦。是滴,我們今天來寫寫用空間換時間的線性排序。

說之前我們先來回顧一下之前的排序算法,最好的時間復雜度為 O(nlogn) ,且都基于元素之間的比較來進行排序。

我們來說一下非基于元素比較的排序算法,且時間復雜度為 O(n),時間復雜度是線性的,所以我們稱其為線性排序算法。

其優勢在于在對一定范圍內的整數排序時,它的復雜度為Ο(n+k),此時的 k 則代表整數的范圍??煊谌魏我环N比較類排序算法,不過也是需要犧牲一些空間來換取時間。

下面我們先來看看什么是計數排序,這個計數的含義是什么?

我們假設某一分店共有 10 名員工,

工齡分別為 1,2,3,5,0,2,2,4,5,9

那么我們將其存在一個長度為 10 的數組里,,但是我們注意,我們數組此時存的并不是元素值,而是元素的個數。見下圖

09f15c56-a7f9-11eb-9728-12bb97331649.png

注:此時我們這里統計次數的數組長度根據最大值來決定,上面的例子中最大值為 9 ,則長度為 9 + 1 = 10。暫且先這樣理解,后面會對其優化 。

我們繼續以上圖的例子來說明,在該數組中,索引代表的為元素值(也就是上面例子中的工齡),數組的值代表的則是元素個數(也就是不同工齡出現的次數)。

即工齡為 0 的員工有 1 個, 工齡為 1 的員工有 1 個,工齡為 2 的員工有 3 個 。。。

然后我們根據出現次數將其依次取出看看是什么效果。

0,1,2,2,2,3,4,5,5,9

我們發現此時元素則變成了有序的,但是這并不是排序,只是簡單的按照統計數組的下標,輸出了元素值,并沒有真正的給原始數組進行排序。

這樣操作之后我們不知道工齡屬于哪個員工。

見下圖

0a30bfea-a7f9-11eb-9728-12bb97331649.png

舉例

雖然喵哥和杰哥工齡相同,如果我們按照上面的操作輸出之后,我們不能知道工齡為 4 的兩個員工,哪個是喵哥哪個是杰哥。

所以我們需要借助其他方法來對元素進行排序。

大家還記不記得我們之前說過的前綴和,下面我們通過上面統計次數的數組求出其前綴和數組。

0a4cf3d6-a7f9-11eb-9728-12bb97331649.png

因為我們是通過統計次數的數組得到了前綴和數組,那么我們來分析一下 presum 數組里面值的含義。

例如我們的 presum[2] = 5 ,代表的則是原數組小于等于 2 的值共有 5 個。presum[4] = 7 代表小于等于 4 的元素共有 7 個。

是不是感覺計數排序的含義要慢慢顯現出來啦。

其實到這里我們已經可以理解的差不多了,還差最后一步,

此時我們要從后往前遍歷原始數組,然后將遍歷到的元素放到臨時數組的合適位置,并修改 presum 數組的值,遍歷結束后則達到了排序的目的。

這時有人要問了,為什么我們要從后往前遍歷呢?

這個問題的答案,我們等下說,繼續往下看吧。

0a583e94-a7f9-11eb-9728-12bb97331649.png

計數排序

我們從后往前遍歷,nums[9] = 9,則我們拿該值去 presum 數組中查找,發現 presum[nums[9]] = presum[9] = 10 ,

大家還記得我們 presum 數組里面每個值的含義嗎,我們此時 presum[9] = 10,則代表在數組中,小于等于的數共有 10 個,則我們要將他排在臨時數組的第 10 個位置,也就是 temp[9] = 9。

我們還需要干什么呢?我們想一下,我們已經把 9 放入到 temp 數組里了,已經對其排好序了,那么我們的 presum 數組則不應該再統計他了,則將相應的位置減 1 即可,也就是 presum[9] = 10 - 1 = 9;

0a79d392-a7f9-11eb-9728-12bb97331649.png

下面我們繼續遍歷 5 ,然后同樣執行上訴步驟

0aa1f8f4-a7f9-11eb-9728-12bb97331649.png

我們繼續查詢 presum 數組,發現 presum[5] = 9,則說明小于等于 5 的數共有 9 個,我們將其放入到 temp 數組的第 9 個位置,也就是

temp[8] = 5。然后再將 presum[5] 減 1 。

0aba5ae8-a7f9-11eb-9728-12bb97331649.png

是不是到這里就理解了計數排序的大致思路啦。

那么我們為什么需要從后往前遍歷呢?我們思考一下,如果我們從前往后遍歷,相同元素的話,前面的元素則會先歸位再減一,這樣則會使計數排序變成不穩定的排序算法。

這個排序的過程像不像查字典呢?通過查詢 presum 數組,得出自己應該排在臨時數組的第幾位。然后再修改下字典,直到遍歷結束。

那么我們先來用動畫模擬一下我們這個 bug 版的計數排序,加深理解。

注:我們得到 presum 數組的過程在動畫中省略。直接模擬排序過程。

計數排序

但是到現在就完了嗎?顯然沒有,我們思考下這個情況。

假如我們的數字為 90,93,94,91,92 如果我們根據上面方法設置 presum 數組的長度,那我們則需要設置數組長度為 95(因為最大值是94),這樣顯然是不合理的,會浪費掉很多空間。

還有就是當我們需要對負數進行排序時同樣會出現問題,因為我們求次數的時候是根據 nums[index] 的值來填充 presum 數組的,所以當 nums[index] 為負數時,填充 presum 數組時則會報錯。

此時通過最大值來定義數組長度也不合理。

所以我們需要采取別的方法來定義數組長度。

下面我們來說一下偏移量的概念。

例如 90,93,94,91,92,我們 可以通過 max ,min 的值來設置數組長度即 94 - 90 + 1 = 5 。偏移量則為 min 值,也就是 90。那么我們的 90 則對應索引 0 。

見下圖。

0afe7e08-a7f9-11eb-9728-12bb97331649.png

這樣我們填充 presum 數組時就不會出現浪費空間的情況了,負數?出現負數的情況當然也可以。繼續看

例如:-1,-3,0,2,1

0b08c994-a7f9-11eb-9728-12bb97331649.png

一樣可以,哦了,到這里我們就搞定了計數排序,下面我們來看一哈代碼吧。

class Solution {

public int[] sortArray(int[] nums) {

int len = nums.length;

if (nums.length 《 1) {

return nums;

}

//求出最大最小值

int max = nums[0];

int min = nums[0];

for (int x : nums) {

if (max 《 x) max = x;

if (min 》 x) min = x;

}

//設置 presum 數組長度,然后求出我們的前綴和數組,

//這里我們可以把求次數數組和前綴和數組用一個數組處理

int[] presum = new int[max-min+1];

for (int x : nums) {

presum[x-min]++;

}

for (int i = 1; i 《 presum.length; ++i) {

presum[i] = presum[i-1]+presum[i];

}

//臨時數組

int[] temp = new int[len];

//遍歷數組,開始排序,注意偏移量

for (int i = len-1; i 》= 0; --i) {

//查找 presum 字典,然后將其放到臨時數組,注意偏移度

int index = presum[nums[i]-min]-1;

temp[index] = nums[i];

//相應位置減一

presum[nums[i]-min]--;

}

//copy回原數組

System.arraycopy(temp,0,nums,0,len);

return nums;

}

}

好啦,這個排序算法我們已經搞定了,下面我們來扒一扒它。

計數排序時間復雜度分析

我們的總體運算量為 n+n+k+n ,總體運算是 3n + k 所以時間復雜度為 O(N+K);

計數排序空間復雜度分析

我們用到了輔助數組,空間復雜度為 O(n)

計數排序穩定性分析

穩定性在我們最后存入臨時數組時有體現,我們當時讓其放入臨時數組的合適位置,并減一,所以某元素前面的相同元素,在臨時數組,仍然在其前面。所以計數排序是穩定的排序算法。

雖然計數排序效率不錯但是用到的并不多。

這是因為其當數組元素的范圍太大時,并不適合計數排序,不僅浪費時間,效率還會大大降低。

當待排序的元素非整數時,也不適用,大家思考一下這是為什么呢?好啦,今天的文章就到這啦,我們下期再見,拜了個拜

巨人的肩膀

算法導論

極客時間數據結構與算法之美
編輯:lyn

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • 計數
    +關注

    關注

    1

    文章

    57

    瀏覽量

    20315
  • 排序
    +關注

    關注

    0

    文章

    32

    瀏覽量

    9821
  • 排序算法
    +關注

    關注

    0

    文章

    53

    瀏覽量

    10211

原文標題:計數排序真的不重要?

文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數據結構】歡迎添加關注!文章轉載請注明出處。

收藏 人收藏

    評論

    相關推薦
    熱點推薦

    九進制計數電路仿真設計

    九進制計數電路仿真
    發表于 06-09 14:48 ?0次下載

    低成本電源排序器解決方案

    絕大多數負載點DC-DC轉換器可以將上一個轉換器的電源就緒輸出連接至下一個轉換器的使能輸入,實現上電排序。這種方法只適合比較簡單的設計,不能滿足多數現代微處理器和DSP的要求一這類器件要求斷電順序必須與上電順序相反。許多廠商針對這類應用推出了可編程排序IC,但器件價格較為
    的頭像 發表于 05-21 09:55 ?414次閱讀
    低成本電源<b class='flag-5'>排序</b>器解決方案

    淺談直流有刷電機驅動及調速技術

    ,圖1 為 H 橋電機驅動 電路示意圖 : 圖1 H橋電機驅動電路示意圖 點擊下方附件查看全文*附件:20250307_淺談直流有刷電機驅動及調速技術.docx
    發表于 03-07 15:24

    攻克反光難題,整箱礦泉水高速精準計數

    在工業生產中,一次性進行大量計數的應用場景非常廣泛。比如制藥生產的藥粒計數、食品加工、電子制造行業微小電子計數。這些場景不僅要求計數工具具備高精度和高速度,還要求能夠應對各種復雜環境和
    的頭像 發表于 01-14 07:34 ?354次閱讀
    攻克反光難題,整箱礦泉水高速精準<b class='flag-5'>計數</b>

    詳解Linux sort命令之掌握排序技巧與實用案例

    排序,與-g區別為不轉為浮點數 -g –general-number-sort 按通用數值排序,支持科學計數法 -f –ignore-case 忽略大小寫,默認大小寫字母不同 -k –key=POS1
    的頭像 發表于 01-09 10:10 ?817次閱讀

    TimSort:一個在標準函數庫中廣泛使用的排序算法

    在計算機科學的領域,排序算法是每位學生必學的基礎,而排序的需求是每位程序員在編程過程中都會遇到的。 在你輕松調用 .sort() 方法對數據進行排序時,是否曾好奇過,這個簡單的方法背后使用的是哪種
    的頭像 發表于 01-03 11:42 ?493次閱讀

    雷擊計數器的概述與應用分析

    雷擊計數器 是一種用于監測和記錄電力系統、通信系統、建筑物等關鍵設施遭受雷擊次數的設備。它能夠有效地幫助管理人員掌握雷電活動的情況,以便進行預防性維護和風險評估。雷擊計數器根據工作原理可以分為無源
    的頭像 發表于 10-21 10:31 ?701次閱讀
    雷擊<b class='flag-5'>計數</b>器的概述與應用分析

    時間復雜度為 O(n^2) 的排序算法

    作者:京東保險 王奕龍 對于小規模數據,我們可以選用時間復雜度為 O(n2) 的排序算法。因為時間復雜度并不代表實際代碼的執行時間,它省去了低階、系數和常數,僅代表的增長趨勢,所以在小規模數據情況下
    的頭像 發表于 10-19 16:31 ?1636次閱讀
    時間復雜度為 O(n^2) 的<b class='flag-5'>排序</b>算法

    74ls163是幾進制同步計數

    74LS163 是一個十進制同步計數器,它是一個集成電路(IC),用于數字電路中進行計數操作。它是一個4位二進制計數器,但由于其設計,它可以很容易地被配置為一個十進制計數器。這意味著它
    的頭像 發表于 10-18 13:54 ?2537次閱讀

    淺談基于物聯網的智能路燈系統-盾華電子智慧路燈解決方案

    淺談基于物聯網的智能路燈系統-盾華電子智慧路燈解決方案
    的頭像 發表于 10-11 10:08 ?813次閱讀
    <b class='flag-5'>淺談</b>基于物聯網的智能路燈系統-盾華電子智慧路燈解決方案

    TPS54120排序和跟蹤

    電子發燒友網站提供《TPS54120排序和跟蹤.pdf》資料免費下載
    發表于 10-10 10:54 ?0次下載
    TPS54120<b class='flag-5'>排序</b>和跟蹤

    正交解碼計數器卡

    正交解碼計數器卡
    發表于 09-06 11:41 ?0次下載

    計數器的特點和參數

    計數器作為一種常用的電子元件,在電子設備和系統中扮演著至關重要的角色。它們不僅用于存儲和增減數字值,還廣泛應用于時序和頻率測量、事件計數、控制步進電機和伺服系統、錯誤檢測和糾正以及計算機數據存儲和操作等領域。以下將詳細闡述計數
    的頭像 發表于 08-29 14:54 ?2313次閱讀

    計數傳感器是開關量還是模擬量

    計數傳感器是一種用于檢測和計數物體數量的傳感器,它可以將物體的數量轉換為電信號輸出。計數傳感器在工業自動化、物流、包裝、醫療等領域有著廣泛的應用。計數傳感器按照其輸出信號的類型可以分為
    的頭像 發表于 07-25 09:50 ?912次閱讀

    計數器同步和異步怎么判斷

    計數器同步和異步是數字電路設計中的一個重要概念,它們在很多應用場景中都扮演著關鍵角色。 一、計數器概述 計數器是一種常見的數字電路,它可以對輸入信號進行計數,并將
    的頭像 發表于 07-23 11:14 ?2427次閱讀