桶排序
概念
桶排序，核心思想是將要排序的數(shù)據(jù)分到幾個(gè)有序的桶里较性，每個(gè)桶里的數(shù)據(jù)再單獨(dú)進(jìn)行排序用僧。桶內(nèi)排序之后，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出赞咙，組成的序列就是有序的责循。
應(yīng)用場景
桶排序比較適合用在外部排序中。所謂的外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤中人弓，數(shù)據(jù)量比較大沼死，內(nèi)存有限，無法將數(shù)據(jù)全部加載到內(nèi)存中崔赌。
計(jì)數(shù)排序
概念
計(jì)數(shù)排序其實(shí)是桶排序的一種特殊情況意蛀。桶的個(gè)數(shù)n與最大值是k相等，省掉桶內(nèi)排序的時(shí)間健芭。
計(jì)數(shù)排序中的“計(jì)數(shù)”指的是通過桶和原數(shù)組县钥，能夠轉(zhuǎn)化為有序的。
應(yīng)用場景
計(jì)數(shù)排序只能用在數(shù)據(jù)范圍不大的場景中慈迈。并且計(jì)數(shù)排序只能給非負(fù)整數(shù)排序若贮，如果數(shù)據(jù)是其他類型，要轉(zhuǎn)化為非負(fù)整數(shù)痒留。
基數(shù)排序
概念
根據(jù)數(shù)據(jù)的每一位來排序谴麦，到達(dá)最終有序。
應(yīng)用場景
基數(shù)排序?qū)σ判虻臄?shù)據(jù)是有要求的伸头，需要可以分割出獨(dú)立的“位”來比較匾效，而且位之間有遞進(jìn)關(guān)系。除此之外恤磷，每一位的數(shù)據(jù)范圍不能太大面哼，要可以用線性排序算法來排序。
課后思考
假設(shè)我們現(xiàn)在需要對(duì)D扫步，a魔策，F(xiàn)，B河胎，c闯袒，A，z這個(gè)字符串進(jìn)行排序，要求將其中所有小寫字母都排在大寫字母的前面政敢，但小寫字母內(nèi)部和大寫字母內(nèi)部不要求有序原茅。比如經(jīng)過排序之后為a，c堕仔，z擂橘，D，F(xiàn)摩骨，B通贞，A，這個(gè)如何來實(shí)現(xiàn)呢恼五？如果字符串中存儲(chǔ)的不僅有大小寫字母昌罩，還有數(shù)字。要將小寫字母的放到前面灾馒，大寫字母放在最后茎用，數(shù)字放在中間，不用排序算法睬罗，又該怎么解決呢轨功？
直接劃分桶，小寫字母容达、數(shù)字古涧、大寫字母三個(gè)桶，遍歷字符串花盐，把字母放進(jìn)各自的桶里羡滑，然后再把小寫字母、數(shù)字算芯、大寫字母三個(gè)桶直接合并柒昏。
