JS實現插入排序

tolerious 發布于2019-08-22 18:31 / 1963人閱讀

摘要：但是，插入排序真的一無是處嗎答案是否定的，插入排序在實踐中的使用頻率是很高的，在一些場景下，甚至展現出完勝高級排序的效率。那么插入排序實際上就是每次將一個數插入到有序的數組中去初始一個數字自然有序。

直接插入排序的時間復雜度為 O(n^2) ，相較于復雜度為 O(nlogn) 的快速排序、歸并排序、堆排序、希爾排序，插入排序可謂相形見絀。但是，插入排序真的一無是處嗎? 答案是否定的，插入排序在實踐中的使用頻率是很高的，在一些場景下，甚至展現出完勝高級排序的效率。下面我們一起來看看。

由于插入排序的實現很簡單，首先直接放出代碼：

function insertSort(arr) {
  let length = arr.length;
  for(let i = 1; i < length; i++) {
    let temp = arr[i];
    let j = i;
    for(; j > 0; j--) {
      if(temp >= arr[j-1]) {
        break;      // 當前考察的數大于前一個數，證明有序，退出循環
      }
      arr[j] = arr[j-1]; // 將前一個數復制到后一個數上
    }
    arr[j] = temp;  // 找到考察的數應處于的位置
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10]
console.log(insertSort(arr));

插入排序的思路跟整理撲克牌是一樣的，即每次拿到一張牌，按大小順序將其插入到合適的位置。那么插入排序實際上就是：每次將一個數插入到有序的數組中去(初始一個數字自然有序)。

下面以實例結合代碼來分析一個插入排序的過程：

由于第一個數 6 是自然有序的，所以我們從第二個數 5 開始考察，將 5 取出與它的前一個數 6 比較，5 < 6，將 6 復制到 5 的位置，5 向前移動繼續比較，此時 5 已經處于數組第一位，第一次排序結束，將 5 放入當前位置；

此時 [5, 6] 已經構成有序數組，考察 4，將 4 取出與它的前一個數 6 比較，4 < 6，將 6 復制到 4 的位置；4 向前移與 5 比較，4 < 5，將 5 復制到前一個 6 的位置，此時 4 處于數組第一位，第二趟排序結束。

后面的排序過程與前面分析的過程一致，總結一下就是：不斷將大于當前考察對象的數后移一位，直到找到考察對象應該處于的位置。有一個需要注意的點是，考察對象不一定是要一直向前移動到數組第一個位置才結束一趟排序，如果中間找到了合適的位置，這趟排序是可以提前終止的。
舉例：

這一點正是插入排序的精髓所在！如果對一個已經有序的數組使用插入排序，插入排序只會遍歷數組一遍，時間復雜度退化為 O(n)；可以想象，如果對一個接近有序的數組使用插入排序，其效率是非常可觀的，而很多時候我們處理的數據是接近有序的，只需調整一些無序項，所以插入排序是很有用的。

云服務器 GPU云服務器實現插入排序用php實現插入排序 js實現table排序插入排序

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

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

排序算法分析總結（附js實現）

摘要：本文對一些排序算法進行了簡單分析，并給出了的代碼實現。平均時間復雜度不好分析，它是冒泡排序是穩定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復雜度是的排序算法。歸并排序，會將數組從中間分成左右兩部分。本文對一些排序算法進行了簡單分析，并給出了 javascript 的代碼實現。因為本文包含了大量的排序算法，所以分析不會非常詳細，適合有對排序算法有一定了解的同學。本文內容其實不...

liaoyg8023 2019-08-23 17:11 評論0 收藏0
排序算法速度測試（插入排序、二分法插入、選擇排序、快速排序、堆排序）js實現

摘要：公共函數庫用于取出隨機排列的數字原數組給原數組賦值排序算法插入排序時間復雜度二分法插入排序選擇排序快速排序一堆排序測試用例插入排序時間測試二分法插入排序時間測試選擇排序時間測試快速排序時間測試一堆公共函數庫（用于取出隨機排列的數字） module.exports={ randomIntegerArray:function(count){ var origina...

mochixuan 2019-08-20 16:04 評論0 收藏0
JS中可能用得到的全部的排序算法

本篇有7k+字, 系統梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復雜的排序實現，如果喜歡請點贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導讀排序算法可以稱得上是我的盲點, 曾幾何時當我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內心是奔潰的(啥是快排, 我只知道...

verano 2019-08-20 15:08 評論0 收藏0
JS實現希爾排序

摘要：希爾排序本質上是一種插入排序，但是對數列進行了等間隔分組處理，在每一組中做插入排序，這一優化使得時間復雜度降到了以下。希爾排序本質上是一種插入排序，但是對數列進行了等間隔分組處理，在每一組中做插入排序，這一優化使得時間復雜度降到了O(n^2)以下。基本思想希爾排序是按一定的間隔對數列進行分組，然后在每一個分組中做插入排序；隨后逐次縮小間隔，在每一個分組中做插入排序...直到間隔等...

chadLi 2019-08-22 18:31 評論0 收藏0
用js寫插入排序和選擇排序

摘要：總結一下，插入排序優于選擇排序。插入排序可以提前終止內層循環，如果數組近乎有序，那么效率會很高。我的寫的不是最好的，僅僅是解釋概念，有興趣的同學可以自己寫一個更好的插入排序和選擇排序。我覺得作為前端學學算法也是有益處的吧，所以今天就先來講講最基礎的排序算法。提升我們程序員的內功~ 插入排序插入排序是n^2的基礎排序方法，大致思想是假設一個數組的前n個元素已經有序，然后考慮把第n+1...

SHERlocked93 2019-08-22 16:37 評論0 收藏0