簡明算法: 插入排序(javascript描述)

Guakin_Huang 發布于2019-08-22 15:20 / 745人閱讀

摘要：懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。所有范例一律從小到大排序插入排序的思路可以參考抓撲克牌假定我們已有的撲克牌已經有序，現在抓了一張新牌，我們需要插入到適當的位置以保持隊列依然有序。

懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。

（所有范例一律從小到大排序）

插入排序的思路可以參考抓撲克牌：假定我們已有的撲克牌已經有序，現在抓了一張新牌，我們需要插入到適當的位置以保持隊列依然有序。

插入排序

給定數組：

var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ];

算法描述：

當數組只有一個元素時，我們認為它有序(廢話)；所以起始從i=1開始，既抓第二張牌后，選擇適當的位置；此時我們將第二張牌與第一張牌比較，由于26比54小，所以將54移動到第二個位置，最后將新牌既26放到首位，此時隊列前兩位有序：

[ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ]

現在i=2，既93與前一張比較，93比54大，所以不需要繼續向前比較了，保持不動即可；因為前兩位有序，93既然比54大，自然比54之前的任意元素大；此時隊列前3位有序；

[ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ]

現在i=3，既17依次與前一張比較，17與93比較，將93移動到后一位；17與54比較，54移動到后一位；17與26比較，26移動到后一位；最后隊列到達頂點，將17放到隊首；此時隊列前4位依然有序；

[ 17, 26, 54, 93, 77, 31, 44, 88, 55, 20 ]

然后我們重復1、2、3步驟，直到整個數組有序;

第1輪: [ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ]
第2輪: [ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ]
第3輪: [ 17, 26, 54, 93, 77, 31, 44, 88, 55, 20 ]
第4輪: [ 17, 26, 54, 77, 93, 31, 44, 88, 55, 20 ]
第5輪: [ 17, 26, 31, 54, 77, 93, 44, 88, 55, 20 ]
第6輪: [ 17, 26, 31, 44, 54, 77, 93, 88, 55, 20 ]
第7輪: [ 17, 26, 31, 44, 54, 77, 88, 93, 55, 20 ]
第8輪: [ 17, 26, 31, 44, 54, 55, 77, 88, 93, 20 ]
第9輪: [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]

算法實現:

function insert(list) {
  // 數組第一位有序，從第二位開始
  for (let i = 1; i < list.length; i++) {
    let t = list[i];
    let j = i - 1;
    // 從i-1依次向前遍歷，因為i之前的隊列有序，只要t比之前的元素小，都需要依次向后順移一位
    for (; j >= 0 && t < list[j]; j--) {
      list[j + 1] = list[j];
    }
    // 不滿足條件時 說明j要么為-1，要么list[j] >= t，所以賦值索引為j+1
    list[j + 1] = t;
  }
}

// 測試
var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ];
insert(list);
console.log(list);
// [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]

GPU云服務器云服務器插入排序算法 java插入排序算法插入排序實現插入排序

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

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

簡明算法: 選擇排序(javascript描述)

摘要：懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。所有范例一律從小到大排序選擇排序比冒泡的改進是，不會頻繁交換元素，而只是記錄索引，最后再交換。懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。（所有范例一律從小到大排序）選擇排序比冒泡的改進是，不會頻繁交換元素，而只是記錄索引，最后再交換。選擇排序給定數組： var list = [ 54, 26, 93...

Miyang 2019-08-22 15:09 評論0 收藏0
簡明算法: 冒泡排序(javascript描述)

懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。（所有范例一律從小到大排序）冒泡排序給定數組： var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ]; 算法描述：將第一個元素與第二個元素對比，此時第一個元素比第二個元素大，交換他們，這樣較大的元素就位于第二個位置了; list = [ 26, 54, 93, 17, 77...

liukai90 2019-08-22 15:09 評論0 收藏0
常用排序算法之JavaScript實現

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

jerry 2019-08-21 12:27 評論0 收藏0
算法：排序算法總結（JavaScript描述）

摘要：二代碼簡單選擇排序一分析循環次，每一次的當前項與其之后的項作比較，找出其中最小的那個，與當前項交換。二代碼希爾排序是一種改進版的插入排序，縮小增量排序。這樣做的目的是因為，直接插入排序在序列基本有序時效率最高。排序算法平均情況最好情況最壞情況輔助空間穩定性冒泡排序 O(n^2) O(n) O(n^2) O(1) 穩定簡單選擇排序 O(n^2) O(n^2)...

dkzwm 2019-08-23 11:45 評論0 收藏0
javascript插入排序

摘要：算法原理插入排序是一種簡單直觀的排序算法。插入排序在實現上，通常采用排序，因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。新元素插入當前位置。算法原理插入排序是一種簡單直觀的排序算法。它的工作原理非常類似于我們抓撲克牌。對于未排序的數據（右手抓到的牌），在已排序序列（左后已經排好序的牌）中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采...

warnerwu 2019-08-26 12:10 評論0 收藏0