基數(shù)排序 Radix Sort 與 JS實現(xiàn)

一些概念
  • 該算法是穩(wěn)定的排序法抄淑;
  • 在所有的情況下觉至,時間復(fù)雜度均為O(nlog(p)k),空間復(fù)雜度為O(n*p)
    (其中K為關(guān)鍵詞位數(shù)助赞,p為數(shù)據(jù)字符數(shù)(即基數(shù)radix));
  • 若n很大袁勺,p固定或很小雹食,此方法將很有效。
  • 基數(shù)排序不需要進行元素間的比較期丰,屬于分配/分布排序群叶;
  • 根據(jù)起始方向可分為 最高位優(yōu)先 MSD 和 最低位優(yōu)先 LSD

使用JS實現(xiàn)了一下,大概是結(jié)合若干隊列钝荡,使用LSD的方式街立,從低位到高位遍歷排序,最后返回排序結(jié)果埠通;

var getNum = function(num,n){//獲取num在指定位置的數(shù)值
  return Math.floor(num/Math.pow(10,n))%10;
}
var getMaxLength = function(nums){//獲取最大數(shù)位(不考慮小數(shù)
  var i, max = 0;
  for(i=0;i<nums.length;i++){
    if(nums[i].toString().length > max){
      max = nums[i].toString().length;
    }
  }
  return max;
};
var Queue = function(){
  //棧的實現(xiàn)(略)
};
var radix_sort = function(arr){
  var i, j, max_length = getMaxLength(arr), queues = [];

  //初始化排序隊列
  for(i=0;i<10;i++){
    queues[i] = new Queue();
  }

  //打印未排序數(shù)據(jù)
  console.log('Before sorting:');
  console.log(arr);
  
  //使用LSD模式遍歷排序各數(shù)位
  for(i=0;i<max_length;i++){
    //數(shù)據(jù)按位分配
    for(j=0;j<arr.length;j++){
      queues[getNum(arr[j],i)].enqueue(arr[j]);
    }
    //更新某一位排序后的數(shù)據(jù)
    arr = [];
    for(j=0;j<10;j++){
      while(!queues[j].isEmpty()){
        arr.push(queues[j].dequeue());
      }
    }
    //打印某一位排序后的數(shù)據(jù)
    console.log('sorting '+ i + ' :');
    console.log(arr);
  }
  return arr;
}

測試數(shù)據(jù):

var arr = [91, 46, 85, 15, 92, 35, 31, 22];
sort(arr);

測試結(jié)果:



2017.04.12
復(fù)習(xí)后更新一個版本

function radixSort(arr,n,radix){
    if(!radix){//默認(rèn)為十進制
        radix = 10;
    }
    if(!n){//如果未指定關(guān)鍵詞位數(shù)將自動使用首個元素的位數(shù)作為n
        n = arr[0].toString().length;
        console.log('auto n : '+n);
    }
    var i,j,tmp,num,queues=[],q=arr.slice();
    for(i=0;i<radix;i++){
        queues.push([]);//生成Q[0]~Q[radix-1]
    }
    for(i=0;i<n;i++){//LSD低位起始
        while(q.length>0){
            tmp = q.shift();
            num = Math.floor(tmp/Math.pow(radix,i)%radix);//獲取某位數(shù)值
            //這里這個轉(zhuǎn)換只能搞得動十進制= =其他就會有問題 因為不能直接用其他進制來進行運算 所以考慮使用字符串處理
            queues[num].push(tmp);
        }
        console.log('round '+i+' with queues : '+queues);
        for(j=0;j<radix;j++){//重構(gòu)q
            while(queues[j].length>0){
                q.push(queues[j].shift());
            }
        }
        console.log('round '+i+' q sorted : '+q);
    }
    return q;
}

測試結(jié)果:

三位數(shù)排序測試結(jié)果
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末赎离,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子植阴,更是在濱河造成了極大的恐慌蟹瘾,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件掠手,死亡現(xiàn)場離奇詭異憾朴,居然都是意外死亡,警方通過查閱死者的電腦和手機喷鸽,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門众雷,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人做祝,你說我怎么就攤上這事砾省。” “怎么了混槐?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵编兄,是天一觀的道長。 經(jīng)常有香客問我声登,道長狠鸳,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任悯嗓,我火速辦了婚禮件舵,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘脯厨。我一直安慰自己铅祸,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布合武。 她就那樣靜靜地躺著临梗,像睡著了一般涡扼。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上夜焦,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天壳澳,我揣著相機與錄音,去河邊找鬼茫经。 笑死巷波,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的卸伞。 我是一名探鬼主播抹镊,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼荤傲!你這毒婦竟也來了垮耳?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤遂黍,失蹤者是張志新(化名)和其女友劉穎终佛,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體雾家,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡铃彰,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了芯咧。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片牙捉。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖敬飒,靈堂內(nèi)的尸體忽然破棺而出邪铲,到底是詐尸還是另有隱情灿渴,我是刑警寧澤嘀韧,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站旨别,受9級特大地震影響英染,放射性物質(zhì)發(fā)生泄漏阴孟。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一税迷、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧锹漱,春花似錦箭养、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽喝检。三九已至,卻和暖如春撼泛,著一層夾襖步出監(jiān)牢的瞬間挠说,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工愿题, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留损俭,地道東北人。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓潘酗,卻偏偏與公主長得像杆兵,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子仔夺,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 概述排序有內(nèi)部排序和外部排序琐脏,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序,而外部排序是因排序的數(shù)據(jù)很大缸兔,一次不能容納全部的...
    Luc_閱讀 2,280評論 0 35
  • 總結(jié)一下常見的排序算法日裙。 排序分內(nèi)排序和外排序。內(nèi)排序:指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序惰蜜。外排序:指在排序...
    jiangliang閱讀 1,354評論 0 1
  • 概述:排序有內(nèi)部排序和外部排序昂拂,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序,而外部排序是因排序的數(shù)據(jù)很大蝎抽,一次不能容納全部...
    每天刷兩次牙閱讀 3,733評論 0 15
  • Ba la la la ~ 讀者朋友們政钟,你們好啊,又到了冷鋒時間樟结,話不多說养交,發(fā)車! 1.冒泡排序(Bub...
    王飽飽閱讀 1,801評論 0 7
  • 小編在CTF“戰(zhàn)斗”平臺上發(fā)布了一道瓢宦,看一眼毀一眼的碎连,xxx公司信息查詢系統(tǒng)。 題目 :如下lag格式:ctf{一...
    實驗吧閱讀 2,653評論 0 1