js實(shí)現(xiàn)幾種常見(jiàn)算法

代碼如下:

//js實(shí)現(xiàn)選擇排序
function selectSort(arr) {
    var len = arr.length;
    for (var i = 0; i < arr.length - 1; i++) {
        var minIndex = i;
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            var temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    console.log(arr)
}

//js實(shí)現(xiàn)插入排序
function insertSort(arr) {
    var len = arr.length;
    for (var i = 1; i < len; i++) {
        var insertValue = arr[i];
        var insertIndex = i - 1;
        while (insertIndex >= 0 && arr[insertIndex] > insertValue) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        if (insertIndex != i - 1) {
            arr[insertIndex + 1] = insertValue;
        }
    }
}

//js實(shí)現(xiàn)希爾排序(移動(dòng)法)
function shellSort(arr) {
    var len = arr.length;
    //必須向下取整嫉髓,不然gap是個(gè)小數(shù)观腊,現(xiàn)象古怪
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (var i = gap; i < len; i++) {
            //插入的索引
            var index = i - gap;
            //插入值
            var val = arr[i];
            while (index >= 0 && arr[index] > val) {
                arr[index + gap] = arr[index];
                index -= gap;
            }
            if (index != i - gap) {
                arr[index + gap] = val;
            }
        }
    }
}

//快速排序
function quickSort(arr, left, right) {
    //終止遞歸
    if (left > right) {
        return;
    }
    var l = left;
    var r = right;
    var base = arr[left];
    var temp = 0;
    //完成值交換
    while (l != r) {
        //從右找比基準(zhǔn)值大的
        while (arr[r] >= base && l < r) {
            r--;
        }
        //從左找比基準(zhǔn)小的值
        while (arr[l] <= base && l < r) {
            l++;
        }
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
    //講基準(zhǔn)值與終點(diǎn)值交換
    arr[left] = arr[l];
    arr[l] = base;
    //向左遞歸
    quickSort(arr, left, l - 1);
    //向右遞歸
    quickSort(arr, r + 1, right);
}

//隨機(jī)快排,降低最壞時(shí)間復(fù)雜度出現(xiàn)
//1.獲取隨機(jī)索引
//low低位算行,high高位
function getRandomIndex (low, high) {
    var randomNum = Math.floor(Math.random()*high);
    return randomNum % (high - low + 1);
}

//2.獲取隨機(jī)索引梧油,并交換和第一個(gè)元素的值(在知道第一個(gè)元素比較小的時(shí)候用會(huì)很好)
function randomQuickSort (arr,left,right){
    var temp = arr[0];
    var index = getRandomIndex(left,right);
    arr[0] = arr[index];
    arr[index] = temp;
    quickSort(arr,left,right);
}

//歸并排序
//1.分
//arr,排序數(shù)組州邢,left左值儡陨,right右值,temp臨時(shí)數(shù)組
function sort (arr,left,right,temp) {
    if(left >= right)return;
    var mid = left + Math.floor((right - left)/2);
    sort(arr,left,mid,temp);
    sort(arr,mid+1,right,temp);
    merge(arr,left,mid,right,temp);
}

//2.并
function merge (arr,left,mid,rightBound,temp){
    var l = left;
    var r = mid + 1;
    var k = left;
    //填充臨時(shí)數(shù)組
    while(l <= mid && r <= rightBound){
        if(arr[l] <= arr[r]){
            temp[k++] = arr[l++];
        }else{
            temp[k++] = arr[r++];
        }
    }
    //將沒(méi)有比較到的元素填充到臨時(shí)數(shù)組
    while(l <= mid){
        temp[k++] = arr[l++];
    }
    while(r <= rightBound){
        temp[k++] = arr[r++];
    }
    //將臨時(shí)數(shù)據(jù)填充到原始數(shù)組里
    for(var m = 0; m <= rightBound; m++){
        arr[m] = temp[m];
    }
}

常用的算法特性:

名稱(chēng) 平均時(shí)間復(fù)雜度 最壞時(shí)間復(fù)雜度 最好時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性
選擇 n^2 n^2 n^2 1 不穩(wěn)
冒泡 n^2 n^2 n^2 1 穩(wěn)
+插入 n^2 n^2 n^2] 1 穩(wěn)
+堆 n*(log n) n*(log n) n*(log n) 1 不穩(wěn)
希爾 n^1.3 n^2 n 1 不穩(wěn)
+歸并 n*(log n) n*(log n) n*(log n) n 穩(wěn)
+快排 n*(log n) n^2 n*(log n) n*(log n) 不穩(wěn)
n + k n^2 n n + k 穩(wěn)
計(jì)數(shù) n + k n + k n + k n + k 穩(wěn)
基數(shù) n * k n * k n * k n + k 穩(wěn)

算法長(zhǎng)時(shí)間不寫(xiě)就容易忘記量淌,建議大家有空多寫(xiě)寫(xiě)骗村,對(duì)于我們解決問(wèn)題思路的養(yǎng)成也很有幫助。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末呀枢,一起剝皮案震驚了整個(gè)濱河市胚股,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌裙秋,老刑警劉巖琅拌,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異摘刑,居然都是意外死亡进宝,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)泣侮,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)即彪,“玉大人,你說(shuō)我怎么就攤上這事活尊×バ#” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵蛹锰,是天一觀的道長(zhǎng)深胳。 經(jīng)常有香客問(wèn)我,道長(zhǎng)铜犬,這世上最難降的妖魔是什么舞终? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任轻庆,我火速辦了婚禮,結(jié)果婚禮上敛劝,老公的妹妹穿的比我還像新娘余爆。我一直安慰自己,他們只是感情好夸盟,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布蛾方。 她就那樣靜靜地躺著,像睡著了一般上陕。 火紅的嫁衣襯著肌膚如雪桩砰。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天释簿,我揣著相機(jī)與錄音亚隅,去河邊找鬼。 笑死庶溶,一個(gè)胖子當(dāng)著我的面吹牛煮纵,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播渐尿,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼醉途,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了砖茸?” 一聲冷哼從身側(cè)響起隘擎,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎凉夯,沒(méi)想到半個(gè)月后货葬,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡劲够,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年震桶,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片征绎。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡蹲姐,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出人柿,到底是詐尸還是另有隱情柴墩,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布凫岖,位于F島的核電站江咳,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏哥放。R本人自食惡果不足惜歼指,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一爹土、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧踩身,春花似錦胀茵、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至赁濒,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間孟害,已是汗流浹背拒炎。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留挨务,地道東北人击你。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像谎柄,于是被迫代替她去往敵國(guó)和親丁侄。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

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

  • Swift1> Swift和OC的區(qū)別1.1> Swift沒(méi)有地址/指針的概念1.2> 泛型1.3> 類(lèi)型嚴(yán)謹(jǐn) 對(duì)...
    cosWriter閱讀 11,113評(píng)論 1 32
  • 每天進(jìn)步一點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)~~從開(kāi)始只能寫(xiě)幾句話朝巫、模仿別人的觀點(diǎn)鸿摇,到現(xiàn)...
    一個(gè)帥氣的名字呀閱讀 18,106評(píng)論 4 31
  • 又到了一個(gè)特別的節(jié)日,今天雖不在父親身邊劈猿,但這幾日里腦子都是父親的畫(huà)面拙吉,在休息的日子里總有更多時(shí)間用來(lái)回顧和總結(jié)自...
    劉紅的香氣世界閱讀 461評(píng)論 0 0
  • 在沒(méi)有讀《財(cái)務(wù)自由之路》之前筷黔,對(duì)于投資的理解略有狹隘。簡(jiǎn)單粗暴的將所有投入資金的行為都定義為投資行為仗颈,舉例來(lái)說(shuō)包括...
    刀仔的仔閱讀 450評(píng)論 2 3
  • 除了編譯時(shí)加上-g選項(xiàng)外佛舱,需要考慮gcc和gdb的兼容性問(wèn)題,很可能gcc更新后與gdb不兼容挨决。
    WebSSO閱讀 913評(píng)論 0 0