建站
咨詢
售后
建站咨詢
新聞中心
這篇文章將為大家詳細(xì)講解有關(guān)web開發(fā)中計(jì)數(shù)排序的示例分析，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。
成都創(chuàng)新互聯(lián)是創(chuàng)新、創(chuàng)意、研發(fā)型一體的綜合型網(wǎng)站建設(shè)公司，自成立以來公司不斷探索創(chuàng)新，始終堅(jiān)持為客戶提供滿意周到的服務(wù)，在本地打下了良好的口碑，在過去的10余年時(shí)間我們累計(jì)服務(wù)了上千家以及全國(guó)政企客戶，如木托盤等企業(yè)單位，完善的項(xiàng)目管理流程，嚴(yán)格把控項(xiàng)目進(jìn)度與質(zhì)量監(jiān)控加上過硬的技術(shù)實(shí)力獲得客戶的一致稱譽(yù)。
計(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ǔ)在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
算法步驟
花O(n)的時(shí)間掃描一下整個(gè)序列 A，獲取最小值 min 和最大值 max
開辟一塊新的空間創(chuàng)建新的數(shù)組 B，長(zhǎng)度為 ( max - min + 1)
數(shù)組 B 中 index 的元素記錄的值是 A 中某元素出現(xiàn)的次數(shù)
最后輸出目標(biāo)整數(shù)序列，具體的邏輯是遍歷數(shù)組 B，輸出相應(yīng)元素以及對(duì)應(yīng)的個(gè)數(shù)
算法演示
排序動(dòng)畫過程解釋
首先，掃描一下整個(gè)序列
獲得最小值為 2 ，最大值為 7
新建數(shù)組包含 2~7 的元素
再次掃描序列，將序列的值放置在新建數(shù)組中
掃描數(shù)字 5，數(shù)組中 index 為 3 的值為 5，次數(shù)為 1
掃描數(shù)字 3，數(shù)組中 index 為 1 的值為 3，次數(shù)為 1
掃描數(shù)字 4，數(shù)組中 index 為 2 的值為 4，次數(shù)為 1
掃描數(shù)字 7，數(shù)組中 index 為 5 的值為 7，次數(shù)為 1
掃描數(shù)字 2，數(shù)組中 index 為 0 的值為 2，次數(shù)為 1
掃描數(shù)字 4，數(shù)組中 index 為 2 的值為 4，次數(shù)為 2
掃描數(shù)字 3，數(shù)組中 index 為 1 的值為 3，次數(shù)為 2
按照這種節(jié)奏，掃描結(jié)束后，新建數(shù)組中存放了整個(gè)序列以及每個(gè)數(shù)字出現(xiàn)的次數(shù)
最后輸出目標(biāo)整數(shù)序列
輸出數(shù)字 2，同時(shí)數(shù)組中 index 為 0 的值為 2 的元素次數(shù)變?yōu)?0
輸出數(shù)字 3，同時(shí)數(shù)組中 index 為 1 的值為 3 的元素次數(shù)變?yōu)?1
同樣的操作，整個(gè)序列就完全輸出了
代碼實(shí)現(xiàn)
為了更好的讓讀者用自己熟悉的編程語言來理解動(dòng)畫，筆者將貼出多種編程語言的參考代碼，代碼全部來源于網(wǎng)上。
Go代碼實(shí)現(xiàn)
Java代碼實(shí)現(xiàn)
Python代碼實(shí)現(xiàn)
JavaScript代碼實(shí)現(xiàn)
關(guān)于“web開發(fā)中計(jì)數(shù)排序的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。
名稱欄目：web開發(fā)中計(jì)數(shù)排序的示例分析
當(dāng)前URL：http://fisionsoft.com.cn/article/ipipec.html
