常用排序算法之JavaScript實(shí)現(xiàn)


作為一名程序員迂苛,算法是一個(gè)沒(méi)法回避的話(huà)題,因?yàn)樗梢哉f(shuō)是專(zhuān)業(yè)與不專(zhuān)業(yè)的一條分界線(xiàn)弃揽。想要在未來(lái)有更高的技術(shù)造詣脯爪,學(xué)會(huì)數(shù)據(jù)結(jié)構(gòu)算法知識(shí)是必須的】笪ⅲ互聯(lián)網(wǎng)技術(shù)發(fā)展到今天痕慢,已經(jīng)有很多算法了,而排序算法算是最好的入門(mén)算法涌矢,因?yàn)樗容^簡(jiǎn)單掖举,而且能讓你迅速了解計(jì)算機(jī)的計(jì)算思維方式。學(xué)習(xí)了常用排序算法之后娜庇,我決定做個(gè)總結(jié)塔次。


0.算法的特性

輸入:一個(gè)算法必須有零個(gè)或以上輸入量方篮。
輸出:一個(gè)算法應(yīng)有一個(gè)或以上輸出量。
明確性:算法的描敘必須無(wú)歧義励负,實(shí)際運(yùn)行結(jié)果是確定的
有限性:必須在有限個(gè)步驟內(nèi)結(jié)束
有效性: 又稱(chēng)可行性,能夠被執(zhí)行者實(shí)現(xiàn)
————高德納《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》

算法的學(xué)習(xí)最重要的是學(xué)會(huì)計(jì)算機(jī)的思維方式藕溅,這是精髓也是難點(diǎn)。

  • 當(dāng)你遇到思路障礙怎么辦?
  • 將抽象的問(wèn)題轉(zhuǎn)化為具體的問(wèn)題
  • 將沒(méi)見(jiàn)過(guò)的問(wèn)題轉(zhuǎn)化為見(jiàn)過(guò)的問(wèn)題

本人的學(xué)習(xí)方法是先用偽代碼實(shí)現(xiàn)或者畫(huà)流程圖梳理一遍思路继榆,再用JS實(shí)現(xiàn)具體細(xì)節(jié)巾表。

算法流程圖.jpg

1. 冒泡算法(BUBBLE)

冒泡算法用通俗一點(diǎn)的話(huà)說(shuō),可以理解為“一個(gè)教官(計(jì)算機(jī))伸出雙手略吨,從頭開(kāi)始集币,按順序依次選擇兩個(gè)人排列站位”。
專(zhuān)業(yè)的理解應(yīng)該是晋南,計(jì)算機(jī)遍歷整個(gè)數(shù)組惠猿,每次選擇兩個(gè)數(shù)進(jìn)行排序,小的放前面大的往后放负间,重復(fù)這個(gè)步驟直到不再需要交換了偶妖,也就是說(shuō)數(shù)組已經(jīng)排列完成。每比較一輪政溃,都會(huì)選出最大的一個(gè)放到當(dāng)前排列數(shù)組的最后趾访。

1.首選選中兩個(gè)數(shù),準(zhǔn)備進(jìn)行比較

冒泡1.PNG

2. 7>3董虱,所以7往后放扼鞋,再往后選擇7和30比較

冒泡2.PNG

3. 以此類(lèi)推比較完第一輪,最大的40被放到了最后


冒泡3.PNG

4. 重復(fù)進(jìn)行前三個(gè)步驟愤诱,最后就會(huì)得到一組從小到大排列的數(shù)組云头。


冒泡4.PNG

實(shí)現(xiàn)代碼

function sort(array){
    for(i=0;i<array.length;i++){
        for(j=0;j<array.length-1;j++){
            if(array[j]<=array[j+1]){

            }else{
                swap(array,j,j+1)
            }
        }
    }
    return array
}
function swap(array,a,b){
    var temp=array[a]
    array[a]=array[b]
    array[b]=temp
}
console.log(sort([3,5,2,21,1]))
console.log(sort([1,3,3,1,1]))
console.log(sort([1]))
console.log(sort([]))

2選擇排序(SELECT)

選擇排序可以通俗理解為第一個(gè)人指著后面的人說(shuō),你們中最小的站在我前面來(lái)淫半。
專(zhuān)業(yè)的理解:每一次標(biāo)記待排序數(shù)據(jù)元素的第一個(gè)元素為被比較元素溃槐,然后往后遍歷,選出最小的存放在序列的起始位置科吭,直到全部待排序的數(shù)據(jù)元素排完昏滴。每一輪遍歷完,都會(huì)選出當(dāng)前數(shù)組里最小的放在最前面对人。

  1. 標(biāo)記第一個(gè)元素谣殊,拿后面的元素與它比較


    選擇1.PNG

    2. 選出了當(dāng)前待排數(shù)組里最小的元素


    選擇2.PNG
    3. 將最初標(biāo)記的元素與最小元素交換位置,一輪遍歷結(jié)束牺弄。下一輪標(biāo)記21姻几。
    選擇3.PNG

    4. 重復(fù)以上步驟,經(jīng)過(guò)多輪比較得到一組從小到大排列的數(shù)組。


    選擇4.PNG

實(shí)現(xiàn)代碼

function sort(array) {
    var indexofMin,i,j
    for(i=0;i<array.length;i++){
           indexofMin=i
       for(j=i+1;j<array.length;j++){
                if(array[j]<array[indexofMin]){
                    indexofMin=j
                }if(indexofMin!==i){
                    swap(array,i,indexofMin)
                }
       }
        
    }
   return array
}
function swap(array,a,b){
    var temp=array[a]
    array[a]=array[b]
    array[b]=temp
}
console.log(sort([3,5,2,21,1]))
console.log(sort([1,3,3,1,1]))
console.log(sort([1]))
console.log(sort([]))

3. 插入排序(INSERT)

插入排序通俗理解:“起牌算法”鲜棠,和打撲克牌時(shí)起牌方法基本一樣肌厨。我們手里已經(jīng)有一副牌,然后選擇一張牌找到它應(yīng)該放的位置豁陆,放入柑爸,這樣就能將一張張牌都放到正確的位置了。
專(zhuān)業(yè)理解:將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中盒音,從而得到一個(gè)新的表鳍、個(gè)數(shù)加一的有序數(shù)據(jù),算法適用于少量數(shù)據(jù)的排序祥诽。是穩(wěn)定的排序方法譬圣。

  1. 第一輪標(biāo)記48,往前看14與48比較


    插入1.PNG

    2. 雄坪,48>14厘熟,不需要變換位置


    插入2.PNG
    3.第二輪標(biāo)記25,往前看與25比較
    插入3.PNG

    4.48>25维哈,把它們倆換位置绳姨,25繼續(xù)與前面的14比較


    插入4.PNG
    5. 25>14,不用交換阔挠,此時(shí)25在前兩個(gè)元素中應(yīng)該放的位置已經(jīng)確定飘庄,放入此位置。第三輪標(biāo)記24
    插入5.PNG
    6. 24分別與前三個(gè)元素比較购撼,比25和48小跪削,所以預(yù)備放在它們之前
    插入6.PNG
    7. 25與剩下的14比較,大于14迂求,所以確定最終位置之后碾盐,插入。
    插入7.PNG
    8. 重復(fù)以上步驟揩局,經(jīng)過(guò)多輪比較得到一組從小到大排列的數(shù)組廓旬。
    插入8.PNG

實(shí)現(xiàn)代碼


var numbers = [21,34,1,3,53,2]
var temp,i,j
for(i=1;i<numbers.length;i++){
    temp=numbers[i]
    for(j=i-1;j>=0&&temp<numbers[j];j--){
        
        numbers[j+1]=numbers[j]
    }
    numbers[j+1]=temp
}
console.log(numbers)

快速排序(QUICK)

快速排序,它又稱(chēng)為自私算法谐腰,它優(yōu)先讓每個(gè)元素找到自己所在的位置,每次排序都實(shí)現(xiàn)“比我大的都在我右邊涩盾,比我小的都在我左邊”而不去計(jì)較它們的位置關(guān)系十气。

  1. 第一輪選擇第一個(gè)元素,然后依次拿后面的元素與它比較


    快速1.PNG

    2. 在比較的過(guò)程中春霍,將后面的元素分成兩部分放置砸西,比34大的放一邊,比34小的放另一邊


    快速2.PNG
    3. 都比較完之后,將34放到中間
    快速3.PNG

    4. 第二輪選擇11


    快速4.PNG
    5. 將34之前的元素與11進(jìn)行比較芹枷,然后重復(fù)比較步驟衅疙,把11放到它的位置
    快速6.PNG
    6. 重復(fù)以上步驟,經(jīng)過(guò)多輪比較得到一組從小到大排列的數(shù)組鸳慈。
    快速7.PNG

實(shí)現(xiàn)代碼

function sort(array){
    if(array.length<=1){
        return array;
    }
    var len = Math.floor(array.length/2);
    var cur = array.splice(len,1);
    var left = [];
    var right = [];
    for(var i=0;i<array.length;i++){
        if(cur>array[i]){
            left.push(array[i]);
        }else{
            right.push(array[i]);
        }
    }
    return sort(left).concat(cur,sort(right));
}

時(shí)間復(fù)雜度

  • 選擇排序饱溢、冒泡排序和插入
    n+(n-1)+(n-2)+(n-3)···=n^2
  • 快速排序
    • nlog2n
    • 快速排序有個(gè)缺點(diǎn),如果給定的數(shù)組是已經(jīng)排好的或者是反序的就不能造成達(dá)到快速的目的了走芋,那么此時(shí)它的時(shí)間復(fù)雜度跟前三種一樣绩郎。解決方案是使用隨機(jī)快速排序,即 不從第一個(gè)開(kāi)始標(biāo)記翁逞。

其它排序

除了以上幾種排序之外肋杖,還有歸并排序(MERGE)、統(tǒng)計(jì)排序(COUNT)挖函、基數(shù)排序(RADIX)等状植。了解詳情請(qǐng)點(diǎn)擊:[visualgo]

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市怨喘,隨后出現(xiàn)的幾起案子津畸,更是在濱河造成了極大的恐慌,老刑警劉巖哲思,帶你破解...
    沈念sama閱讀 212,718評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件洼畅,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡棚赔,警方通過(guò)查閱死者的電腦和手機(jī)帝簇,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,683評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)靠益,“玉大人丧肴,你說(shuō)我怎么就攤上這事‰屎螅” “怎么了芋浮?”我有些...
    開(kāi)封第一講書(shū)人閱讀 158,207評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀(guān)的道長(zhǎng)壳快。 經(jīng)常有香客問(wèn)我纸巷,道長(zhǎng),這世上最難降的妖魔是什么眶痰? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,755評(píng)論 1 284
  • 正文 為了忘掉前任瘤旨,我火速辦了婚禮,結(jié)果婚禮上竖伯,老公的妹妹穿的比我還像新娘存哲。我一直安慰自己因宇,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,862評(píng)論 6 386
  • 文/花漫 我一把揭開(kāi)白布祟偷。 她就那樣靜靜地躺著察滑,像睡著了一般。 火紅的嫁衣襯著肌膚如雪修肠。 梳的紋絲不亂的頭發(fā)上贺辰,一...
    開(kāi)封第一講書(shū)人閱讀 50,050評(píng)論 1 291
  • 那天,我揣著相機(jī)與錄音氛赐,去河邊找鬼魂爪。 笑死,一個(gè)胖子當(dāng)著我的面吹牛艰管,可吹牛的內(nèi)容都是我干的滓侍。 我是一名探鬼主播,決...
    沈念sama閱讀 39,136評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼牲芋,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼撩笆!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起缸浦,我...
    開(kāi)封第一講書(shū)人閱讀 37,882評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤夕冲,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后裂逐,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體歹鱼,經(jīng)...
    沈念sama閱讀 44,330評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,651評(píng)論 2 327
  • 正文 我和宋清朗相戀三年卜高,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了弥姻。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,789評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡掺涛,死狀恐怖庭敦,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情薪缆,我是刑警寧澤秧廉,帶...
    沈念sama閱讀 34,477評(píng)論 4 333
  • 正文 年R本政府宣布,位于F島的核電站拣帽,受9級(jí)特大地震影響疼电,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜减拭,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,135評(píng)論 3 317
  • 文/蒙蒙 一澜沟、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧峡谊,春花似錦、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,864評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至啥纸,卻和暖如春号杏,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背斯棒。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,099評(píng)論 1 267
  • 我被黑心中介騙來(lái)泰國(guó)打工盾致, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人荣暮。 一個(gè)月前我還...
    沈念sama閱讀 46,598評(píng)論 2 362
  • 正文 我出身青樓庭惜,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親穗酥。 傳聞我的和親對(duì)象是個(gè)殘疾皇子护赊,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,697評(píng)論 2 351

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

  • 某次二面時(shí),面試官問(wèn)起Js排序問(wèn)題砾跃,吾絞盡腦汁回答了幾種骏啰,深感算法有很大的問(wèn)題,所以總計(jì)一下抽高! 排序算法說(shuō)明 (1...
    流浪的先知閱讀 1,190評(píng)論 0 4
  • 排序的基本概念 在計(jì)算機(jī)程序開(kāi)發(fā)過(guò)程中判耕,經(jīng)常需要一組數(shù)據(jù)元素(或記錄)按某個(gè)關(guān)鍵字進(jìn)行排序,排序完成的序列可用于快...
    Jack921閱讀 1,421評(píng)論 1 4
  • 不知道什么時(shí)候開(kāi)始翘骂,上海每年總有那么幾十天壁熄,斷斷續(xù)續(xù)的下雨。 等待的時(shí)候雏胃,隔著車(chē)窗请毛,看燈影霓虹,恰好 Alan 的...
    wingfish閱讀 95評(píng)論 0 0
  • 今天成長(zhǎng)營(yíng)的小任務(wù)是:最近你在拖延的事情有哪些瞭亮?大部分的小伙伴都提到了整理打掃方仿。原來(lái)大家還真就差不多,我在整理打掃...
    小easy閱讀 227評(píng)論 5 1
  • https://www.zhihu.com/question/20011323/answer/119365301 ...
    靖蘭亭閱讀 495評(píng)論 0 49