作為一個(gè)前端,排序算法你有了解過(guò)嗎?

lansheng228 發(fā)布于2019-08-22 17:29 / 588人閱讀

摘要：前言前天看到知乎上有一篇文章在吐槽阮一峰老師的快速排序算法這里插一句題外話我覺(jué)得人非圣賢孰能無(wú)過(guò)盡信書(shū)不如無(wú)書(shū)學(xué)習(xí)的過(guò)程也就是不斷發(fā)現(xiàn)錯(cuò)誤改正錯(cuò)誤的過(guò)程有人幫我們糾正了這個(gè)錯(cuò)誤我們應(yīng)該開(kāi)心但是我覺(jué)得不應(yīng)該批判阮一峰老師他也在不斷地學(xué)習(xí)不斷地

前言

前天看到知乎上有一篇文章在吐槽阮一峰老師的快速排序算法,這里插一句題外話,我覺(jué)得人非圣賢孰能無(wú)過(guò),盡信書(shū)不如無(wú)書(shū),學(xué)習(xí)的過(guò)程也就是不斷發(fā)現(xiàn)錯(cuò)誤改正錯(cuò)誤的過(guò)程,有人幫我們糾正了這個(gè)錯(cuò)誤我們應(yīng)該開(kāi)心,但是我覺(jué)得不應(yīng)該批判阮一峰老師,他也在不斷地學(xué)習(xí),不斷地糾錯(cuò)成長(zhǎng),所以大家都一樣,無(wú)所謂誤導(dǎo),如果出錯(cuò)的不是他,是更厲害的牛人呢?JavaScript的作者呢?所以大家都會(huì)出錯(cuò),我們也應(yīng)該多思考,抱著懷疑的態(tài)度接納,時(shí)刻思考這是不是最優(yōu)的解法,還有沒(méi)有更好的呢,我想這才是我們應(yīng)該做的.
而我,作為一個(gè)計(jì)算機(jī)專業(yè)的前端,卻不能很好地實(shí)現(xiàn)各種思想的排序算法,我覺(jué)得很慚愧,所以我就抽時(shí)間仔細(xì)查看了<<數(shù)據(jù)結(jié)構(gòu)與算法分析：C語(yǔ)言描述+中文版.pdf>>這本書(shū),下面我就對(duì)我理解的各種思想的排序算法做一下總結(jié),希望可以給大家一些參考和收獲,如有不妥之處,煩請(qǐng)指出,也可以分享你們覺(jué)得更好地想法,我覺(jué)得大家一起學(xué)習(xí)一起進(jìn)步是最快樂(lè)的事~

1. 應(yīng)當(dāng)熟悉的相關(guān)概念 1.1 時(shí)間復(fù)雜度

(1) 時(shí)間復(fù)雜度的概念
算法的時(shí)間復(fù)雜度是一個(gè)函數(shù),他定性地描述了某個(gè)算法的運(yùn)行時(shí)間,常用大O符號(hào),不包括這個(gè)函數(shù)的低階項(xiàng)和高階項(xiàng)系數(shù).
(2) 計(jì)算方法

一般情況下,算法中基本操作的執(zhí)行次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù),用T(n)表示,若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí),T(n)/f(n)的極限值為不為零的常數(shù),則f(n)是T(n)的同數(shù)量級(jí)函數(shù),記作T(n) = O(f(n)),稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度,簡(jiǎn)稱為時(shí)間復(fù)雜度.

分析: 隨時(shí)模塊n的增大,算法的執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率成正比,所以f(n)越小,算法的時(shí)間復(fù)雜度越低,算法的效率越高.

在計(jì)算時(shí)間復(fù)雜度的時(shí)候,先找出算法的基本操作,然后計(jì)算出基本操作的執(zhí)行次數(shù),找出T(n)的同數(shù)量級(jí)f(n)(它的同數(shù)量級(jí)一般有以下: 1, log?n,n,nlog?n,n的平方,n的三次方),若T(n) / f(n)求極限得到一常數(shù)c,則時(shí)間復(fù)雜度T(n) = O(f(n)):

舉例如下:

for(i = 1; i<= n; i++) {
    for(j = 1; j <= n; j++) {
        c[i][j] = 0;   // 該步驟屬于基本操作的執(zhí)行次數(shù): n的平方
        for( k= 1;k <= n; k++) {
            c[i][j] += a[i][k] * b[k][j];   // 該步驟屬于基本操作的執(zhí)行次數(shù): n的三次方
        }
    }
}

我們可以得到T(n) = n^3 + n^2,我們可以確定n^3為T(mén)(n)的同數(shù)量級(jí),f(n)=n^3;然后T(n) / f(n) = 1 + 1/n 求極限為常數(shù)1,所以該算法的時(shí)間復(fù)雜度為:
T(n) = O(n^3);

說(shuō)明: 為了方便我接下來(lái)都是使用N來(lái)代指數(shù)組元素個(gè)數(shù)的.
我的建議: 我建議大家先看代碼,看不懂代碼的時(shí)候?qū)χa看圖解,這樣方便更好的理解

2. 排序算法 2.1 冒泡排序 2.1.1 主要思想:

冒泡排序的主要思想就是對(duì)一個(gè)長(zhǎng)度為n的數(shù)組進(jìn)行遍歷, i從n-1到1的,數(shù)組的前i個(gè)元素的最大值放在i位置上,假想冒泡排序是一個(gè)豎著的水柱,遍歷的過(guò)程就是,大的值(重的)不斷沉下來(lái),小的值(輕的)不斷浮上去,這樣遍歷結(jié)束后,每個(gè)位置上的值都比他前面的值大,排序結(jié)束.

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

最壞情況下的時(shí)間復(fù)雜度: o(n^2);
最好情況下的時(shí)間復(fù)雜度: o(n^2);

2.1.3 冒泡排序過(guò)程圖解:

2.1.4 代碼實(shí)現(xiàn): 冒泡排序-非遞歸實(shí)現(xiàn)

function bubbleSort(arr) {
    for(var i = arr.length - 1; i > 1; i--) {
        for(var j=0; j < i; j++) {
            if(arr[j] > arr[j+1]) {
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
bubbleSort(arr);  // [8, 21, 32, 34, 51, 64]

冒泡排序-遞歸實(shí)現(xiàn)

function bubbleSort(arr, n) {
    if(n <= 1) {
        return arr;
    } else {
        for(var j=0; j < n - 1; j++) {
            if(arr[j] > arr[j+1]) {
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        return bubbleSort(arr, --n);
    }
}
var arr =  [34,8,64,51,32,21];
bubbleSort(arr, arr.length);  // [8, 21, 32, 34, 51, 64]

2.2 選擇排序 2.2.1 主要思想:

選擇排序的主要思想就是i 從 0 循環(huán)到到length - 1, 依次找出待排數(shù)組中從 i 到 length - 1 位置上的最小值放在 i 位置上.這樣最后得到的數(shù)組就是排好序的數(shù)組了.

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

最壞情況下的時(shí)間復(fù)雜度: o(n^2);
最好情況下的時(shí)間復(fù)雜度: o(n^2);

2.2.3 選擇排序過(guò)程圖解:

2.2.4 代碼實(shí)現(xiàn): 選擇排序-非遞歸實(shí)現(xiàn)

function selectSort(arr) {
    var len = arr.length, min = 0;
    for(var i = 0;i < len - 1; i++) {
        min = i;   // 默認(rèn)最小值的位置
        for(var j = i + 1; j < len; j++){
            if(arr[min] > arr[j]) {
                min = j;
            }
        }
        if(min != i) {
            var temp = arr[min];arr[min] = arr[i]; arr[i] = temp;
        }  
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
selectSort(arr);

選擇排序-遞歸實(shí)現(xiàn)

function selectSort(arr, n, min) {
    var len = arr.length;
    if(n < len - 1) {
        for(var j = n + 1; j < len; j++){
            if(arr[min] > arr[j]) {
                min = j;
            }
        }
        if(min != n) {
            var temp = arr[min];arr[min] = arr[n]; arr[n] = temp;
        } 
        n++;
        return  selectSort(arr, n, min);
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
selectSort(arr, 0, 0);

2.3 插入排序 2.3.1 主要思想:

插入排序有 n-1 趟排序組成,對(duì)于 i=1 到 i=n-1 趟,內(nèi)層循環(huán)j從 i 到 1, 如果這其中有 j-1 位置上的元素大于 i 位置上的元素,就將該元素后移,知道條件不成立退出循環(huán),這個(gè)時(shí)候大的值都被移動(dòng)到后面了,j這個(gè)位置就是i位置上的元素應(yīng)該在的位置.這樣保證了每次循環(huán)i位置前的所有元素都是排好序的,新的循環(huán)就只需要將 i 位置上的元素和 j-1(也就是初始的 i-1) 位置上的元素作比較,如果大于則無(wú)需再往前比較,如果小于則繼續(xù)往前比較后移.

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

最壞情況下的時(shí)間復(fù)雜度: o(n^2);
最好情況下的時(shí)間復(fù)雜度: o(n);

2.3.3 排序過(guò)程圖解:

2.3.4 代碼實(shí)現(xiàn) 插入排序-非遞歸實(shí)現(xiàn)

function insertSort(arr) {
    var n = arr.length,temp = 0;
    for(var i = 1; i < n; i++) {
        temp = arr[i];
        for(j = i; j > 0 && arr[j-1] > temp; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
insertSort(arr);  // [8, 21, 32, 34, 51, 64]

插入排序-遞歸實(shí)現(xiàn)

function insertSort(arr, n) {
    if(n > 0 && n < arr.length){
        var i = j = n, temp = arr[n];
        while(j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
        i++;
        return insertSort(arr, i);
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
insertSort(arr, 1); // [8, 21, 32, 34, 51, 64]; // 這個(gè)函數(shù)的調(diào)用限定了第一次調(diào)用n的值只能傳1

2.4 快速排序

顧名思義,快速排序是在實(shí)踐中最快的已知排序算法,它的平均運(yùn)行時(shí)間是O(Nlog?N).快速排序的關(guān)鍵在于樞紐元的選取,有一種比較推薦的選取方法就是選取左端的值,右端的值,中間位置的值(L(left + right) / 2)這三個(gè)數(shù)的中位數(shù).舉例: 輸入為8,1,4,9,6,3,5,2,7,0, 左邊元素8, 右邊元素0,中間位置上的元素L(0+9)/2是4位置上的元素是6,L在表示向下取整.
8,0,6的中位數(shù),先排序0,6,8, 這三個(gè)數(shù)的中位數(shù)是6.

2.4.1 基本思想

通過(guò)一趟排序?qū)⒁判虻牟糠址指畛瑟?dú)立的兩部分,其中一部分?jǐn)?shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)進(jìn)行快速排序,整個(gè)排序過(guò)程可以遞歸進(jìn)行,依次達(dá)到整個(gè)數(shù)據(jù)變成有序序列.

實(shí)現(xiàn)步驟

第一步: 設(shè)置兩個(gè)變量i,j,排序開(kāi)始的時(shí)候: i=left,j=right-1,left和right分別表示要進(jìn)行快速排序序列的起始索引和結(jié)束索引;

第二步: 從數(shù)組中隨機(jī)選取一個(gè)元素,將其與arr[left]進(jìn)行交換,即privot = arr[left],保證每一次的基準(zhǔn)值都在序列的最左邊;

第三步: 由j開(kāi)始向前搜索,即由后開(kāi)始向前搜索(j--),找到第一個(gè)小于privot 的值arr[j],將arr[i]與arr[j]互換;

第四步: 從i開(kāi)始向后搜索,即由前開(kāi)始向后搜索(i++),找到一個(gè)大于privot 的arr[i],將arr[i]與arr[j]互換;

第五步: 重復(fù)第三步和第四步,直到不滿足i

第六步: 重復(fù)第二步到第四步,依次對(duì)i位置左右兩邊的元素進(jìn)行快速排序,直到left大于等于right為止.

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

平均情況下的時(shí)間復(fù)雜度: o(nlog?n);
最好情況下的時(shí)間復(fù)雜度: o(n);

2.4.3 排序過(guò)程圖解

2.4.4 代碼實(shí)現(xiàn): 快速排序-遞歸實(shí)現(xiàn)

function quickSort(arr, left, right) {
    if(left >= right) return;
    var i = left;
    var j = right - 1;
    var privot = arr[left];
    //console.log(privot);
    while(i < j) {
        while(i= privot) j--;
        arr[i] = arr[j];
        while(i
快速排序-非遞歸實(shí)現(xiàn)
function mainProduce(arr, left, right) {
        var i = left, j = right - 1;
        var rendomIndex = Math.floor(Math.random() * (j - i)) + left;
        var temp = arr[left];arr[left] = arr[rendomIndex];arr[rendomIndex] = temp;
        var privot = arr[left];
        while(i < j) {
            while(i= privot) j--;
            var temp = arr[i];arr[i] = arr[j];arr[j] = temp;
            while(i left + 1) {
                s.push(left);s.push(mid);
            }
            if(mid < right - 1) {
                s.push(mid + 1);s.push(right);
            }
            
            while(s.length !== 0) {
                right = s.pop();
                left = s.pop();
                mid = mainProduce(arr, left, right);
                if(mid > left + 1) {
                    s.push(left);s.push(mid);
                }
                if(mid < right - 1) {
                    s.push(mid + 1);s.push(right);
                }
            }
        }
        return arr;
    }
    var arr = [49,38,65,97,76,13,27,49,55,04];
    quickSort(arr, 0, arr.length);
    
2.5 希爾排序
2.5.1 主要思想
希爾排序是把記錄按照下標(biāo)的一定增量分組,對(duì)每組使用插入排序;隨著增量逐漸減少,分割的數(shù)組越來(lái)越大,當(dāng)增量減至1,整個(gè)數(shù)組排序完成,算法終止.
主要步驟

第一步: 選取一個(gè)增量d,初始值是Math.floor(len/2);
第二步: 然后將數(shù)組中間隔為增量d的組成新的分組,然后對(duì)這個(gè)分組的元素排序,完成排序后,增量除以2得到新的增量;
第三步: 重復(fù)第二步,直到增量為1,間隔為1的元素組成的分組就是整個(gè)數(shù)組,然后再對(duì)整個(gè)數(shù)組進(jìn)行插入排序,得到最后排序后數(shù)組.

希爾排序是不穩(wěn)定的,它在不斷地交換的過(guò)程中會(huì)改變?cè)瓉?lái)相等的元素的順序.
2.5.2 時(shí)間復(fù)雜度
平均情況下的時(shí)間復(fù)雜度: o(nlog?n);
最好情況下的時(shí)間復(fù)雜度: o(n);
2.5.3 排序過(guò)程圖解

圖片源于自百度百科: 圖片來(lái)源
2.5.4 代碼實(shí)現(xiàn):
希爾排序-遞歸實(shí)現(xiàn)
function shellSort(arr, increment) {
    var len = arr.length;
    if(increment > 0) {
        for(var i = increment; i < len; i++) {
            for(var j = i - increment; j >= 0 && arr[j] > arr[j + increment]; j -= increment) {
                    var temp = arr[j];
                    arr[j] = arr[j + increment];
                    arr[j + increment] = temp;
            }
        }
        return shellSort(arr, Math.floor(increment/2));
    }
     return arr; 
}
var arr = [49,38,65,97,76,13,27,49,55,04];
shellSort(arr, Math.floor(arr.length / 2));
 
希爾排序-非遞歸實(shí)現(xiàn)
function shellSort(arr) {
        var len = arr.length;
        for(var increment = Math.floor(len / 2); increment > 0; increment = Math.floor(increment / 2)) {
                for(var i = increment; i < len; i++) {
                        for(var j = i - increment; j >= 0 && arr[j] > arr[j + increment]; j -= increment) {
                                var temp = arr[j];
                                arr[j] = arr[j + increment];
                                arr[j + increment] = temp;
                        }
                }
        }
        return arr;
}
var arr = [49,38,65,97,76,13,27,49,55,04];
shellSort(arr);
 

2.6 歸并排序
2.6.1 主要思想
希爾排序的主要思想就是遞歸將數(shù)組層層分割,直到分割成最小的單元,然后再比較,提供一個(gè)新的空數(shù)組arrayC,將分割的左右兩個(gè)數(shù)組中小的數(shù)放進(jìn)數(shù)組,然后再層層回溯向上合并.得到最終的arrayC就是排序后的數(shù)組.
2.6.2 時(shí)間復(fù)雜度
平均情況下的時(shí)間復(fù)雜度: O(nlog?n);
最好情況下的時(shí)間復(fù)雜度: O(nlog?n) ;
2.6.3 排序過(guò)程圖解

2.6.4 代碼實(shí)現(xiàn):
歸并排序-遞歸實(shí)現(xiàn)
var result = [];
function mergeArray(left, right) {
    result = [];
    while(left.length > 0 && right.length > 0) {
        if(left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
            }
    }
    return result.concat(left).concat(right);
}
function mergerSort(arr) {
    if(arr.length <= 1) {
        return arr;
    }

    var middle = Math.floor(arr.length / 2);
    var left = arr.slice(0, middle);
    var right = arr.slice(middle);
    return mergeArray(mergerSort(left), mergerSort(right));
}
var arr = [49,38,65,97,76,13,27,49,55,04];
mergerSort(arr, 0, arr.length);
 
由于歸并排序的非遞歸實(shí)現(xiàn)比較復(fù)雜,我這里就不做講解了,我覺(jué)得如果真的需要用到,讀者可自行研究.
總結(jié)
這是我寫(xiě)的最用心的一篇博客了,萬(wàn)事開(kāi)頭難,我已經(jīng)開(kāi)頭了,就是一種突破.希望我可以繼續(xù)堅(jiān)持下去,不斷充電,不斷輸出,成為一個(gè)優(yōu)秀的前端工程師,加油 ^-^ ^-^.
  歡迎幫我糾正錯(cuò)誤和有疑問(wèn)的人與我交流, it will be my pleasure.  我的qq號(hào): 2510909248.
推薦閱讀
1) 十大經(jīng)典排序算法總結(jié)（JavaScript描述）

云服務(wù)器 GPU云服務(wù)器作為一個(gè) 前端排序前端冒泡排序排序算法圖解

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/95210.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

lansheng228

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

CSDN去廣告，超清爽界面

閱讀 1752·2021-09-26 09:46
服務(wù)器跟電腦主機(jī)由什么區(qū)別-主機(jī)和服務(wù)器的區(qū)別是什么？

閱讀 3032·2021-09-22 15:55
手把手教你學(xué)Vue-2(組件開(kāi)發(fā))

閱讀 2620·2019-08-30 14:17
express + mock 讓前后臺(tái)并行開(kāi)發(fā)

閱讀 3037·2019-08-26 11:59
React16.2的fiber架構(gòu)

閱讀 1821·2019-08-26 11:35
YAHOO 軍規(guī)

閱讀 3164·2019-08-26 10:45
【Vue原理】Slot - 源碼版之普通插槽

閱讀 3162·2019-08-23 18:28
js監(jiān)聽(tīng)div元素的寬高變化

閱讀 1148·2019-08-23 18:21

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

作為一個(gè)前端,排序算法你有了解過(guò)嗎?

相關(guān)文章

前端面試題大集合：來(lái)自真實(shí)大廠的532道面試題(只有題，沒(méi)有答案)

前端面試題大集合：來(lái)自真實(shí)大廠的532道面試題(只有題，沒(méi)有答案)

前端面試題大集合：來(lái)自真實(shí)大廠的532道面試題(只有題，沒(méi)有答案)

前端面試總結(jié)（at, md）

前端小白的面經(jīng)小記

發(fā)表評(píng)論

0條評(píng)論

lansheng228

男|高級(jí)講師

TA的文章

CSDN去廣告，超清爽界面

服務(wù)器跟電腦主機(jī)由什么區(qū)別-主機(jī)和服務(wù)器的區(qū)別是什么？

手把手教你學(xué)Vue-2(組件開(kāi)發(fā))

express + mock 讓前后臺(tái)并行開(kāi)發(fā)

React16.2的fiber架構(gòu)

YAHOO 軍規(guī)

【Vue原理】Slot - 源碼版之普通插槽

js監(jiān)聽(tīng)div元素的寬高變化

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

作為一個(gè)前端,排序算法你有了解過(guò)嗎?

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！