web開(kāi)發(fā)中計(jì)數(shù)排序的示例分析

這篇文章將為大家詳細(xì)講解有關(guān)web開(kāi)發(fā)中計(jì)數(shù)排序的示例分析，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

計(jì)數(shù)排序

計(jì)數(shù)排序是一種非基于比較的排序算法，其空間復(fù)雜度和時(shí)間復(fù)雜度均為O(n+k)，其中k是整數(shù)的范圍。基于比較的排序算法時(shí)間復(fù)雜度最小是O(nlogn)的。該算法于1954年由 Harold H. Seward 提出。

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

算法步驟

1. 花O(n)的時(shí)間掃描一下整個(gè)序列 A，獲取最小值 min 和最大值 max

2. 開(kāi)辟一塊新的空間創(chuàng)建新的數(shù)組 B，長(zhǎng)度為 ( max - min + 1)

3. 數(shù)組 B 中 index 的元素記錄的值是 A 中某元素出現(xiàn)的次數(shù)

4. 最后輸出目標(biāo)整數(shù)序列，具體的邏輯是遍歷數(shù)組 B，輸出相應(yīng)元素以及對(duì)應(yīng)的個(gè)數(shù)

算法演示

排序動(dòng)畫(huà)過(guò)程解釋

1. 首先，掃描一下整個(gè)序列

2. 獲得最小值為 2 ，最大值為 7

3. 新建數(shù)組包含 2~7 的元素

4. 再次掃描序列，將序列的值放置在新建數(shù)組中

5. 掃描數(shù)字 5，數(shù)組中 index 為 3 的值為 5，次數(shù)為 1

6. 掃描數(shù)字 3，數(shù)組中 index 為 1 的值為 3，次數(shù)為 1

7. 掃描數(shù)字 4，數(shù)組中 index 為 2 的值為 4，次數(shù)為 1

8. 掃描數(shù)字 7，數(shù)組中 index 為 5 的值為 7，次數(shù)為 1

9. 掃描數(shù)字 2，數(shù)組中 index 為 0 的值為 2，次數(shù)為 1

10. 掃描數(shù)字 4，數(shù)組中 index 為 2 的值為 4，次數(shù)為 2

11. 掃描數(shù)字 3，數(shù)組中 index 為 1 的值為 3，次數(shù)為 2

12. 按照這種節(jié)奏，掃描結(jié)束后，新建數(shù)組中存放了整個(gè)序列以及每個(gè)數(shù)字出現(xiàn)的次數(shù)

13. 最后輸出目標(biāo)整數(shù)序列

14. 輸出數(shù)字 2，同時(shí)數(shù)組中 index 為 0 的值為 2 的元素次數(shù)變?yōu)?0

15. 輸出數(shù)字 3，同時(shí)數(shù)組中 index 為 1 的值為 3 的元素次數(shù)變?yōu)?1

16. 同樣的操作，整個(gè)序列就完全輸出了

代碼實(shí)現(xiàn)

為了更好的讓讀者用自己熟悉的編程語(yǔ)言來(lái)理解動(dòng)畫(huà)，筆者將貼出多種編程語(yǔ)言的參考代碼，代碼全部來(lái)源于網(wǎng)上。

Go代碼實(shí)現(xiàn)

Java代碼實(shí)現(xiàn)

Python代碼實(shí)現(xiàn)

JavaScript代碼實(shí)現(xiàn)

關(guān)于“web開(kāi)發(fā)中計(jì)數(shù)排序的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。