時(shí)間復(fù)雜度是線性的，這類排序算法叫做線性排序。
三個(gè)算法是 基于比較的排序算法，不設(shè)計(jì)元素之間的比較操作，所以能做到線性的時(shí)間復(fù)雜度。
桶排序
核心思想是將要排序的數(shù)據(jù)分到幾個(gè)有序的桶內(nèi)，每個(gè)桶內(nèi)的數(shù)據(jù)進(jìn)行單獨(dú)排序，拍好之后把桶內(nèi)的數(shù)據(jù)取出來(lái)，組成的序列就是有序的。時(shí)間復(fù)雜度是O(n).桶內(nèi)部采用的是快速排序手段
首先桶排序要把數(shù)據(jù)進(jìn)行劃分到m個(gè)桶內(nèi)，希望的是桶內(nèi)數(shù)據(jù)是均勻的，并且桶與桶之間有著天然的大小順序。
極端情況下時(shí)間復(fù)雜度會(huì)退化為O(nlog n);
比較適合外部排序。
在進(jìn)行劃分桶數(shù)據(jù)的時(shí)候，可能存在桶數(shù)據(jù)不均勻的情況，可以選擇在多的數(shù)據(jù)桶進(jìn)行繼續(xù)劃分桶，直到桶數(shù)據(jù)可以加載到內(nèi)存中為止。
計(jì)數(shù)排序
桶排序的一種特殊情況。范圍不是很大。最大值是K直接化為K個(gè)桶。桶內(nèi)數(shù)值是相等的。
計(jì)數(shù)排序的原則
- 把一系列的數(shù)字統(tǒng)計(jì)個(gè)數(shù)放在數(shù)組內(nèi)A。
- 依次累加，統(tǒng)計(jì)結(jié)果還是在同一個(gè)數(shù)組中存放A。
- 臨時(shí)數(shù)組C存放排序后的結(jié)果。
- 遍歷最初時(shí)的數(shù)據(jù)B，從A中找到該值。
- A數(shù)組中的值-1就是數(shù)據(jù)B在臨時(shí)數(shù)組C存放的位置。
- 把A數(shù)組中的值減1.
-
循環(huán)這個(gè)過(guò)程
摘自極客時(shí)間
該計(jì)數(shù)規(guī)則只適合 數(shù)據(jù)范圍不大的情景
基數(shù)排序
基數(shù)排序要對(duì)排序的數(shù)據(jù)有要求，分割獨(dú)立的位出來(lái)比較。
從高位開始進(jìn)行比較，高位相同，比較低位。數(shù)據(jù)范圍不能太大。
需要借助桶排序，或者計(jì)數(shù)排序完成每一個(gè)位的排序工作。
實(shí)戰(zhàn)問(wèn)題
100萬(wàn)用戶排序，根據(jù)桶算法，根據(jù)用戶年齡分桶，比如1-120 。那么分為120個(gè)桶。
遍歷元素，放入到桶中既可以得到有序的好的數(shù)據(jù)。
桶中用快排的方式進(jìn)行排序。
