JavaScript的排序算法

booster 發布于2019-08-26 10:34 / 1393人閱讀

摘要：基本概念時間復雜度算法執行所耗費的時間。內排序所有排序操作都在內存中完成。常用的排序算法冒泡排序基本概念依次比較相鄰的兩個數將小數放在前面，大數放在后面。實現原理通過遞歸的方式將數據依次分解為包含較小元素和較大元素的不同子序列。

1：基本概念

時間復雜度：算法執行所耗費的時間。

這個復雜度直接和樣本的個數有關，復雜度反映了算法的性能，一般來說，復雜度越低，算法所消耗的時間越短。

    /* O(N1) */
    for (var i = 0; i < data.length; i++) {
        ...
    }
    
    /* O(N2) */
    for (var i = 0; i < data.length; i++) {
        for (var j = 0; j < data.length; j++) {
            ...
        }
    }

空間復雜度：運行一個程序所需內存的大小。

空間復雜度和時間復雜度是對立的，比如說，時間復雜度越高，空間復雜度越低；反之則相反。

內排序：所有排序操作都在內存中完成。

2：常用的排序算法 冒泡排序（Bubble Sort）

基本概念：依次比較相鄰的兩個數,將小數放在前面，大數放在后面。

時間復雜度：O(N2)。

實現原理：重復的走訪要排序的數列，一次比較兩個元素，大的元素放后面，如果它們的順序錯誤就把它們交換過來。

代碼實現：有兩層循環嵌套，外循環遍歷數組的每一項，內循環用于兩兩元素的比較，每次內循環減1。

    function bubbleSort(arr) {
        var length = arr.length;
        for (var i = 0; i < length; i++) {
            for (var j = 0; j < length - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    [arr[j], arr[j+1]] = [arr[j+1], arr[j]];  
                }
            }
        }
        return arr;
    }

選擇排序（Selection Sort）

時間復雜度：O(N2)。

實現原理：從未排序的序列中找到最小(大)的元素存放到指定的起始位置，再從未排序的序列元素中重復上一步，直至排序完成。

代碼實現：兩層循環嵌套，外循環遍歷數組的每一項，內循環用于找到樣本里面的最小值或者最大值，每次內循環減1。

    function selectionSort(arr) {
        var length = arr.length;
        var minIndex, temp;
        for (var i = 0; i < length - 1; i++) {
            minIndex = i;
            for (var j = i + 1; j < length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
        }
        return arr;
    }

快速排序（Quick Sort）

時間復雜度：O(N * log2N)。

實現原理：通過遞歸的方式將數據依次分解為包含較小元素和較大元素的不同子序列。

代碼實現：找到一個數作為參考，然后比這個數字大的放在數字左邊，比它小的放在右邊，分別再對左右兩邊的序列做相同的操作。

    function partition(arr, low, high) {
      let pivot = arr[low];
      while (low < high) {
        while (low < high && arr[high] > pivot) {
          --high;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) {
          ++low;
        }
        arr[high] = arr[low];
      }
      arr[low] = pivot;
      return low;
    }
    function quickSort(arr, low, high) {
      if (low < high) {
        let pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
      }
      return arr;
    }

插入排序（Insertion Sort）

時間復雜度：O(N2)。

實現原理：構建一個有序序列，未排序數據在已排序序列中從后向前掃描，找到正確位置插入。

代碼實現：兩層循環嵌套，創建已排序數組, 起始包含數組的第一個元素，比這個數字大的放在數字左邊，比它小的放在右邊。

    function insertSort(arr) {
        for(let i = 1; i < arr.length; i++) {
            for(let j = i; j > 0; j--) {
                if(arr[j] < arr[j-1]) {
                    [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
                } else {
                    break;
                }
            }
        }
        return arr;
    }

GPU云服務器云服務器字母的排序算法最好的排序算法選擇排序的算法過程最好的快速排序算法

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

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

深入淺出 JavaScript 的 Array.prototype.sort 排序算法

摘要：快速排序是不穩定的排序算法。瀏覽器的實現不同有什么影響排序算法不穩定有什么影響舉個例子某市的機動車牌照拍賣系統，最終中標的規則為按價格進行倒排序相同價格則按照競標順位即價格提交時間進行正排序。本文要解決的問題 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一種直觀的方式展示 Array.prototype.sort 的時間復雜度，看看它有多快？ 3、...

itvincent 2019-08-21 11:55 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

zhou_you 2019-08-16 10:34 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

caoym 2019-07-31 10:56 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

microcosm1994 2019-08-20 16:30 評論0 收藏0
常用排序算法之JavaScript實現

摘要：代碼實現六堆排序算法簡介堆排序是指利用堆這種數據結構所設計的一種排序算法。九計數排序算法簡介計數排序是一種穩定的排序算法。計數排序不是比較排序，排序的速度快于任何比較排序算法。贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...

jerry 2019-08-21 12:27 評論0 收藏0
優秀程序員都應該學習的 GitHub 上開源的數據結構與算法項目

摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...

cheukyin 2019-08-26 10:17 評論0 收藏0