網上有這么一個段子之前很是流行:老公一定要找程序員,錢多話少死的早?。?!其實最開始聽到這個的時候我是拒絕的。因為我也是程序員呀,But我是程序媛……哈哈O(∩_∩)O。

做編程,新技術一直在不斷不斷地變化,掌握一些基礎是未來學習不斷更新的技術的堅實基礎,尤其是JavaScript,現在不懂JavaScript可以說是寸步難行了吧,講到JavaScript,面試比較多問的除了一些基礎應該就是算法和數據結構了吧。說到數據結構,小萌初看到這個詞的時候,還以為是在說數據庫結構,尷尬ing……(原諒自己了,自己學過PHP,學過數據庫呢……哈哈(^▽^))今天小萌要分享的就是數據結構中的排序算法了,文章末尾有驚喜哦。

做編程,排序是個必然的需求。前端也不例外,雖然不多,但是你肯定會遇到。之前小呆換工作面試的時候有跟小萌講到過排序,但是沒有做過多的記錄,今天小萌就來補上這篇文章,說到排序,除了原生的sort()方法,還有就是JS十大經典算法排序,但是今天小萌不說那么多,只說簡單排序的冒泡排序,選擇排序和插入排序。復雜今天小萌就簡單記錄下這幾種排序,如果有什么不對的地方,還請各位大大指出來。

Sort()排序

sort()的定義和用法

  1. sort() 方法用于對數組的元素進行排序。
  2. 語法如下:arrayObject.sort(sortby)
    sortby可選項。規定排序順序。必須是函數。
  3. 返回值
    為對數組的引用。請注意,數組在原數組上進行排序,不生成副本。
  4. 說明
    如果調用該方法時沒有使用參數,將按字母順序對數組中的元素進行排序,說得更精確點,是按照字符編碼的順序進行排序。要實現這一點,首先應把數組的元素都轉換成字符串(如有必要),以便進行比較。如果想按照其他標準進行排序,就需要提供比較函數,該函數要比較兩個值,然后返回一個用于說明這兩個值的相對順序的數字。比較函數應該具有兩個參數 a 和 b,其返回值如下:
  • 若 a 小于 b,在排序后的數組中 a 應該出現在 b 之前,則返回一個小于 0 的值。
  • 若 a 等于 b,則返回 0。
  • 若 a 大于 b,則返回一個大于 0 的值。
function sort(){
    var arr = new Array(1,35,2,14,7,8,23,6,19,0);
    arr.sort();
    document.writeln(arr);
}
function sort(){
    var arr = new Array(1,2,35,14,7,8,23,6,19,0);
    arr.sort(function(a,b){
        return a-b});
    document.writeln(arr);
}

冒泡排序

思路:依次比較相鄰的兩個元素,如果后一個小于前一個,則交換,這樣從頭到尾一次,就將最大的放到了末尾。要實現上述規則需要用到兩層for循環。但是這樣有個問題,就是循環結束之后需要從頭到尾再來一次,由于每進行一輪,最后的都已經是最大的了,因此后一輪需要比較次數可以比上一次少一個。雖然還是可以從頭到尾來比較,但是后面的比較是沒有意義的無用功,因此為了效率,我們應該對代碼進行優化。優化完的代碼如下:

var arr = new Array(1,35,2,14,7,8,23,6,19,0);
function sort(){
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) { // 相鄰元素兩兩對比
                var temp = arr[j+1];  // 元素交換
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

動圖演示:
冒泡排序

選擇排序

思路:選擇排序的思路就比較簡單了,每次都找一個最大或者最小的排在開始就可以了。首先在未排序序列中找到最?。ù螅┰?,存放到排序序列的起始位置,然后再從剩余未排序元素中繼續尋找最?。ù螅┰?,然后放到已排序序列的末尾;重復第二步,直到所有元素均排序完畢。代碼如下:

var arr = new Array(1,35,2,14,7,8,23,6,19,0);
function sort(){
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 尋找最小的數
                minIndex = j;                 // 將最小數的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

動圖演示:
選擇排序

插入排序

思路:插入排序也比較簡單。就像打撲克摸牌的時候按照牌的大小整理牌一樣,依次將拿到的元素插入到正確的位置即可。代碼如下:

var arr = new Array(1,35,2,14,7,8,23,6,19,0);
function sort(){
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

動圖演示:
插入排序

這三種方法相比呢,冒泡排序是最簡單、最慢的,長度小于7的時候使用情況最佳,快速排序相對來說速度就比較快了, 插入排序呢,比冒泡要快,比快速排序慢,數據量小的時候優勢比較大。

上面三種都是非常簡單的排序方法,簡單的同時呢,效率也會比較低,但是對于我們日常工作應該是沒有問題了,但是如果看官大大rws公司具有大數據的排序,那小萌真的是愛莫能助了……到這里就ending了。如果有什么問題大家請在評論里提出哦……共同進步。

當當當當…你以為真的結束了嗎?NO!福利來了……今天是感恩節,謝謝各位看官大大對小呆小萌博客的支持,特發一個紅包以表謝意,在支付寶紅包輸入口令“小呆小萌??燉幀本涂閃烊『彀病?/p>