国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JavaScript排序,不只是冒泡

leeon / 1445人閱讀

摘要:不過說到排序,最容易想到的就是冒泡排序,選擇排序,插入排序了。一是影響太小,而是我們人的效率問題,一分鐘能從頭寫個冒泡選擇插入的排序方法,而換成是歸并排序呢原文發表在我的博客排序,不只是冒泡,歡迎訪問

非常非常推薦大家去讀一本gitBook上的書 - 十大經典排序算法 : https://sort.hust.cc/ , 本文的動圖和演示代碼均是這里面的。

做編程,排序是個必然的需求。前端也不例外,雖然不多,但是你肯定會遇到。

不過說到排序,最容易想到的就是冒泡排序,選擇排序,插入排序了。

冒泡排序

依次比較相鄰的兩個元素,如果后一個小于前一個,則交換,這樣從頭到尾一次,就將最大的放到了末尾。

從頭到尾再來一次,由于每進行一輪,最后的都已經是最大的了,因此后一輪需要比較次數可以比上一次少一個。雖然你還是可以讓他從頭到尾來比較,但是后面的比較是沒有意義的無用功,為了效率,你應該對代碼進行優化。

圖片演示如下:

代碼實現:

function bubbleSort(arr) {
    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;
}
選擇排序

選擇排序我覺得是最簡單的了,大一學VB的時候,就只記住了這個排序方法,原理非常簡單:每次都找一個最大或者最小的排在開始即可。

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

再從剩余未排序元素中繼續尋找最小(大)元素,然后放到已排序序列的末尾。

重復第二步,直到所有元素均排序完畢。

動圖演示:

代碼演示:

function selectionSort(arr) {
    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;
}
插入排序

插入排序也比較簡單。就像打撲克一樣,依次將拿到的元素插入到正確的位置即可。

將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當成是未排序序列。

從頭到尾依次掃描未排序序列,將掃描到的每個元素插入有序序列的適當位置。(如果待插入的元素與有序序列中的某個元素相等,則將待插入元素插入到相等元素的后面。)

動圖演示:

代碼示例:

function insertionSort(arr) {
    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;
}
簡單的代價是低效

上面三種都是非常簡單的排序方法,簡單的同時呢,效率也會比較低,還是拿這本書里的對比圖來說明:

時間復雜度都高達O(n^2),而它們后面的一些排序算法時間復雜度基本都只有O(n log n)

我的強迫癥又犯了,我想要高效率一點的排序方法。

歸并排序

簡單把這本書的內容過了一遍,當時就理解了這個歸并排序,因此這里就談一下這個歸并排序吧。

基本原理是分治法,就是分開并且遞歸來排序。

步驟如下:

申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合并后的序列;

設定兩個指針,最初位置分別為兩個已經排序序列的起始位置;

比較兩個指針所指向的元素,選擇相對小的元素放入到合并空間,并移動指針到下一位置;

重復步驟 3 直到某一指針達到序列尾;

將另一序列剩下的所有元素直接復制到合并序列尾。

動圖演示:

代碼示例:

function mergeSort(arr) {  // 采用自上而下的遞歸方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

既然是個愛折騰的人,折騰了總得看看效果吧。

效率測試

由于我學這個來進行排序不是對簡單數組,數組內都是對象,要對對象的某個屬性進行排序,還要考慮升降序。

因此我的代碼實現如下:

/**
 * [歸并排序]
 * @param  {[Array]} arr   [要排序的數組]
 * @param  {[String]} prop  [排序字段,用于數組成員是對象時,按照其某個屬性進行排序,簡單數組直接排序忽略此參數]
 * @param  {[String]} order [排序方式 省略或asc為升序 否則降序]
 * @return {[Array]}       [排序后數組,新數組,并非在原數組上的修改]
 */
var mergeSort = (function() {
    // 合并
    var _merge = function(left, right, prop) {
        var result = [];

        // 對數組內成員的某個屬性排序
        if (prop) {
            while (left.length && right.length) {
                if (left[0][prop] <= right[0][prop]) {
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }
            }
        } else {
            // 數組成員直接排序
            while (left.length && right.length) {
                if (left[0] <= right[0]) {
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }
            }
        }

        while (left.length)
            result.push(left.shift());

        while (right.length)
            result.push(right.shift());

        return result;
    };

    var _mergeSort = function(arr, prop) { // 采用自上而下的遞歸方法
        var len = arr.length;
        if (len < 2) {
            return arr;
        }
        var middle = Math.floor(len / 2),
            left = arr.slice(0, middle),
            right = arr.slice(middle);
        return _merge(_mergeSort(left, prop), _mergeSort(right, prop), prop);
    };

    return function(arr, prop, order) {
        var result = _mergeSort(arr, prop);
        if (!order || order.toLowerCase() === "asc") {
            // 升序
            return result;
        } else {
            // 降序
            var _ = [];
            result.forEach(function(item) {
                _.unshift(item);
            });
            return _;
        }
    };
})();

需要對哪個屬性進行排序是不確定,可以隨意指定,因此寫成了參數。有由于不想讓這些東西在每次循環都進行判斷,因此代碼有點冗余。

關于降序的問題,也沒有加入參數中,而是簡單的升序后再逆序輸出。原因是不想讓每次循環遞歸里都去判斷條件,所以簡單處理了。

下面就是見證效率的時候了,一段數據模擬:

var getData = function() {
    return Mock.mock({
        "list|1000": [{
            name: "@cname",
            age: "@integer(0,500)"
        }]
    }).list;
};

上面使用Mock進行了模擬數據,關于Mock : http://mockjs.com/

實際測試來啦:

// 效率測試
var arr = getData();

console.time("歸并排序");
mergeSort(arr, "age");
console.timeEnd("歸并排序");

console.time("冒泡排序");
for (var i = 0, l = arr.length; i < l - 1; ++i) {
    var temp;
    for (var j = 0; j < l - i - 1; ++j) {
        if (arr[j].age > arr[j + 1].age) {
            temp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = temp;
        }
    }
}
console.timeEnd("冒泡排序");

進行了五次,效果如下:

// 歸并排序: 6.592ms
// 冒泡排序: 25.959ms

// 歸并排序: 1.334ms
// 冒泡排序: 20.078ms

// 歸并排序: 1.085ms
// 冒泡排序: 16.420ms

// 歸并排序: 1.200ms
// 冒泡排序: 16.574ms

// 歸并排序: 2.593ms
// 冒泡排序: 12.653ms

最低4倍,最高近16倍的效率之差還是比較滿意的。

雖然1000條數據讓前端排序的可能性不大,但是幾十上百條的情況還是有的。另外由于node,JavaScript也能運行的服務端了,這個效率的提升也還是有用武之地的。

一點疑問

歸并排序里面使用了遞歸,在《數據結構與算法 JavaScript 描述》中,作者給出了自下而上的迭代方法。但是對于遞歸法,作者卻認為:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而,在 JavaScript 中這種方式不太可行,因為這個算法的遞歸深度對它來講太深了。

gitbook上這本書的作者對此有疑問,我也有疑問。

歸并中雖然用了遞歸,但是他是放在return后的呀。關于在renturn后的遞歸是有尾遞歸優化的呀。

關于尾遞歸優化是指:本來外層函數內部再調用一個函數的話,由于外層函數需要等待內層函數返回后才能返回結果,進入內層函數后,外層函數的信息,內存中是必須記住的,也就是調用堆棧。而內部函數放在return關鍵字后,就表示外層函數到此也就結束了,進入內層函數后,沒有必要再記住外層函數內的所有信息。

上面是我的理解的描述,不知道算不算準確。chrome下已經可以開啟尾遞歸優化的功能了,我覺得這個遞歸是不該影響他在JavaScript下的使用的。

最后

有興趣的話,推薦讀讀這本書,進行排序的時候,可以考慮一些更高效的方法。

不過需要注意的是,這些高效率的排序方法,一般都需要相對較多的額外內存空間,需要權衡一下。

另外,非常小規模的數據就沒有必要了。一是影響太小,而是我們人的效率問題,一分鐘能從頭寫個冒泡、選擇、插入的排序方法,而換成是歸并排序呢?

原文發表在我的博客JavaScript排序,不只是冒泡,歡迎訪問!

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/82161.html

相關文章

  • JavaScript實現冒泡排序 可視化

    摘要:說明上次寫了實現冒泡排序,只是簡單的說了冒泡排序算法是什么,怎么實現,這次來實現將冒泡排序的過程展現出來。總結上面的兩個版本的思路基本一樣,用一句話概括就是,記錄冒泡排序所有的改變,將這些改變一步一步的顯示出來。 說明 上次寫了 JavaScript實現冒泡排序 ,只是簡單的說了冒泡排序算法是什么,怎么實現,這次來實現將冒泡排序的過程展現出來。 解釋 先來個簡單的版本,看效果圖 sh...

    RebeccaZhong 評論0 收藏0
  • JavaScript 版各大排序算法

    摘要:推薦一下,,這里還有個可視化的排序博客,各大排序算法的實現都栩栩如生。堆排序堆排序是指利用堆這種數據結構所設計的一種排序算法。共勉參考維基百科排序搜索聊一聊排序算法秒殺種排序算法版排序圖解排序算法實現歡迎來我的博客交流 最近看到了很多公司都在準備明年的實習校招,雖然離三月份還有一段時間,感覺已經可以準備了。在網上看了一些排序算法和數組去重操作,感覺都寫的很好,心血來潮,也來寫一寫。 s...

    FrozenMap 評論0 收藏0
  • JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

    摘要:筆者寫的數據結構與算法之美系列用的語言是,旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面,而,排序之后,在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學好前端,先練好內功,內功不行,就...

    zsy888 評論0 收藏0
  • JavaScript實現的幾種排序

    摘要:冒泡排序原理冒泡排序的過程就是將數組中相鄰的兩個元素進行比較,如果前面的元素比后面的元素要大交換位置,否則位置不變舉個栗子有數組第一輪循環和比較,小于兩者位置不變,接下來和比較,大于,兩者交換位置,接著和比較,兩者交換位置,繼續和比較兩者交 1.冒泡排序 原理:冒泡排序的過程就是將數組中相鄰的兩個元素進行比較,如果前面的元素比后面的元素要大交換位置,否則位置不變;舉個栗子:有數組 ar...

    piapia 評論0 收藏0
  • JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

    摘要:之所以把冒泡排序選擇排序插入排序放在一起比較,是因為它們的平均時間復雜度都為。其中,冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序,也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學好前端,先練好內功,...

    canger 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<