常見前端排序方式對比

godlong_X 發布于2019-08-23 12:00 / 320人閱讀

摘要：首先需要一個自動生成數組的函數自動生成數組的函數執行上面函數，的到的數組長度為，因為執行速度很快，只有長度很大時，才能看到各個方法的執行速度的差別注意到不能簡單的用賦值，否則改變后，到也相應改變了六個相同的數組并且數組長度要足夠大才能對比出

首先需要一個自動生成數組的函數

    // 自動生成數組的函數
    function randomArr (n) {
        let arr = [];
        for (let i = 1; i <= n; i++) {
            arr.push(Math.floor(Math.random() * (i + 1)));
        }
        return arr;
    }

執行上面函數，的到的arr1數組長度為50000，因為js執行速度很快，只有長度很大時，才能看到各個方法的執行速度的差別

注意 arr2到arr6不能簡單的用賦值，否則arr1改變后，arr2到arr6也相應改變了

    
    // 六個相同的數組 并且數組長度要足夠大才能對比出來
    let arr1 = randomArr(50000);
    let arr2 = [...arr1];
    let arr3 = [...arr1];
    let arr4 = [...arr1];
    let arr5 = [...arr1];
    let arr6 = [...arr1];

接下來是我們常見的排序方式

    // 選擇排序
    function pickSort (arr) {
        let temp;
        for (let i = 0; i < arr.length; i++) {
            for (let j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    // 冒泡排序
    function bubleSort (arr) {
        let temp, isSort;
        for (let i = 1; i < arr.length; i++) {
            isSort = false;
            for (let j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    isSort = true;
                }
            }
            if (!isSort) {
                break;
            }
        }
        return arr;
    }

    // 快速排序 快速排序方法同時也是遞歸
    function quickSort (arr) {
        if (arr.length <= 1) {
            return arr;
        }
        let x = arr.splice(0, 1)[0];
        let left = [], right = [];
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] < x) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat([x]).concat(quickSort(right));
    }

    // 插入排序
    function spliceSort (arr) {
        let temp;
        for (let i = 1; i < arr.length; i++) {
            for (let j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break
                }
            }
        }
        return arr;
    }

    // 希爾排序
    function shellSort (arr) {
        let temp;
        let gap = 1;
        while (gap < arr.length) {
            gap = 3 * gap + 1;
        }
        for (; gap > 0; gap = Math.floor(gap / 3)) {
            for (let i = gap; i < arr.length; i ++) {
                for (let j = i; j > 0; j -= gap) {
                    if (arr[j] < arr[j - gap]) {
                        temp = arr[j];
                        arr[j] = arr[j - gap];
                        arr[j - gap] = temp;
                    } else {
                        break
                    }
                }
            }
        }
        return arr;
    }

計算各個方法所花費的時間

最后，需要一個函數調用以上各種排序的方法，并進行時間計算

    // 計算排序時間的函數
    function calcTime (arr, fun) {
        console.time(fun.name);
        let newArr = fun(arr);
        console.timeEnd(fun.name);
    }
    
    // 開始計算
    calcTime(arr1,bubleSort);
    calcTime(arr2,quickSort);
    calcTime(arr3,pickSort);
    calcTime(arr4,spliceSort);
    calcTime(arr5,shellSort);

Array.protype.sort是js自帶排序函數，也可以測試一下速度

    // 看下array.prototype中排序的效率如何
    console.time("Array.prototype.sort");
    arr6.sort(function (a,b) {
        return a-b;
    });
    console.timeEnd("Array.prototype.sort");

計算結果來了

bubleSort: 6846.92724609375ms
quickSort: 342.636962890625ms
pickSort: 5732.3818359375ms
spliceSort: 859.482177734375ms
shellSort: 58.785888671875ms
Array.prototype.sort: 69.878173828125ms

小結

希爾排序 > Array.prototype.sort > 快速排序 > 插入排序 > 選擇排序 > 冒泡排序

云服務器 GPU云服務器 ddos常見攻擊方式常見的數據存儲方式前端排序前端冒泡排序

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

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

初級前端開發面試總結

摘要：前端面試總結先說背景，本人年月畢業，去年十月校招到今年月一直在做前端開發工作，年前打算換工作，就重新梳理下面試考點總結包含基礎，基礎，常見算法和數據結構，框架，計算機網絡相關知識，可能有的點很細，有的點很大，參考個人情況進行總結，方便對知識前端面試總結先說背景，本人2018年7月畢業，去年十月校招到今年10月一直在做前端開發工作，年前打算換工作，就重新梳理下面試考點總結包含： ...

jifei 2019-08-30 15:54 評論0 收藏0
初級前端開發面試總結

摘要：前端面試總結先說背景，本人年月畢業，去年十月校招到今年月一直在做前端開發工作，年前打算換工作，就重新梳理下面試考點總結包含基礎，基礎，常見算法和數據結構，框架，計算機網絡相關知識，可能有的點很細，有的點很大，參考個人情況進行總結，方便對知識前端面試總結先說背景，本人2018年7月畢業，去年十月校招到今年10月一直在做前端開發工作，年前打算換工作，就重新梳理下面試考點總結包含： ...

tigerZH 2019-08-23 14:07 評論0 收藏0
前端之多種排序方式

摘要：前言排序是編程中很基礎卻很有學問的算法。常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。本文主要闡述前端面試中最常問的三種排序冒泡排序選擇排序，其他排序方法詳情點我。冒泡排序算法描述比較相鄰的元素。前言排序是編程中很基礎卻很有學問的算法。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。本文主...

ShevaKuilin 2019-08-26 14:05 評論0 收藏0
深度剖析：如何實現一個 Virtual DOM 算法

摘要：本文所實現的完整代碼存放在。這就是所謂的算法。兩個樹的完全的算法是一個時間復雜度為的問題。如果有差異的話就記錄到一個對象里面。如和的不同，會被所替代。這牽涉到兩個列表的對比算法，需要另外起一個小節來討論。作者：戴嘉華轉載請注明出處并保留原文鏈接（ https://github.com/livoras/blog/issues/13 ）和作者信息。目錄： 1 前言 2 對前端應用狀...

vvpvvp 2019-08-21 10:49 評論0 收藏0
博客 - 收藏集 - 掘金

摘要：技術之類加載機制掘金類加載機制是語言的一大亮點，使得類可以被動態加載到虛擬機中。玩轉仿探探卡片式滑動效果掘金講起本篇博客的歷史起源，估計有一段歷史了。 Java 技術之類加載機制 - Android - 掘金類加載機制是 Java 語言的一大亮點，使得 Java 類可以被動態加載到 Java 虛擬機中。這次我們拋開術語和概念，從例子入手，由淺入深地講解 Java 的類加載機制。本文...

Shimmer 2019-08-16 10:35 評論0 收藏0