建站
咨詢
售后
建站咨詢
新聞中心
有一種很神奇的排序，基數(shù)排序(Radix Sort)，時(shí)間復(fù)雜度為O(n)，今天花1分鐘，通過幾幅圖，爭(zhēng)取讓大家搞懂細(xì)節(jié)。
成都創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站建設(shè)、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的荷塘網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
畫外音：居然還有時(shí)間復(fù)雜度為O(n)的排序算法?
不但有，其實(shí)還有很多。 舉個(gè)栗子：
假設(shè)待排序的數(shù)組arr={72, 11, 82, 32, 44, 13, 17, 95, 54, 28, 79, 56}
基數(shù)排序的兩個(gè)關(guān)鍵要點(diǎn)：
(1)基：被排序的元素的“個(gè)位”“十位”“百位”，暫且叫“基”，栗子中“基”的個(gè)數(shù)是2(個(gè)位和十位);畫外音：來自野史，大神可幫忙修正。
(2)桶：“基”的每一位，都有一個(gè)取值范圍，栗子中“基”的取值范圍是0-9共10種，所以需要10個(gè)桶(bucket)，來存放被排序的元素;
基數(shù)排序的算法步驟為：
- FOR (每一個(gè)基) {
- //循環(huán)內(nèi)，以某一個(gè)“基”為依據(jù)
- 第一步：遍歷數(shù)據(jù)集arr，將元素放入對(duì)應(yīng)的桶bucket
- 第二步：遍歷桶bucket，將元素放回?cái)?shù)據(jù)集arr
- }
更具體的，對(duì)應(yīng)到上面的栗子，“基”有個(gè)位和十位，所以，F(xiàn)OR循環(huán)會(huì)執(zhí)行兩次。
第一次：以“個(gè)位”為依據(jù)。
畫外音：上圖中標(biāo)紅的部分，個(gè)位為“基”。
第一步：遍歷數(shù)據(jù)集arr，將元素放入對(duì)應(yīng)的桶bucket;
操作完成之后，各個(gè)桶會(huì)變成上面這個(gè)樣子，即：個(gè)位數(shù)相同的元素，會(huì)在同一個(gè)桶里。
第二步：遍歷桶bucket，將元素放回?cái)?shù)據(jù)集arr;
畫外音：需要注意，先入桶的元素要先出桶。
操作完成之后，數(shù)據(jù)集會(huì)變成上面這個(gè)樣子，即：整體按照個(gè)位數(shù)排序了。
畫外音：個(gè)位數(shù)小的在前面，個(gè)位數(shù)大的在后面。
第二次：以“十位”為依據(jù)。
畫外音：上圖中標(biāo)紅的部分，十位為“基”。
第一步：依然遍歷數(shù)據(jù)集arr，將元素放入對(duì)應(yīng)的桶bucket;
操作完成之后，各個(gè)桶會(huì)變成上面這個(gè)樣子，即：十位數(shù)相同的元素，會(huì)在同一個(gè)桶里。
第二步：依然遍歷桶bucket，將元素放回?cái)?shù)據(jù)集arr;
操作完成之后，數(shù)據(jù)集會(huì)變成上面這個(gè)樣子，即：整體按照十位數(shù)也排序了。
畫外音：十位數(shù)小的在前面，十位數(shù)大的在后面。
首次按照個(gè)位從小到大，第二次按照十位從小到大，即：排序結(jié)束。
神奇不神奇!!!
幾個(gè)小點(diǎn)：
(1)基的選取，可以先從個(gè)位開始，也可以先從十位開始，結(jié)果是一樣的;
(2)基數(shù)排序，是一種穩(wěn)定的排序;
(3)時(shí)間復(fù)雜度，可以認(rèn)為是線性的O(n); 希望這一分鐘，大家有收獲。
【本文為專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】
文章名稱：這個(gè)排序這么酷，為什么知道的人很少？
文章位置：http://www.5511xx.com/article/cdoiojh.html
