資訊專欄INFORMATION COLUMN
摘要：懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。所有范例一律從小到大排序插入排序的思路可以參考抓撲克牌假定我們已有的撲克牌已經(jīng)有序，現(xiàn)在抓了一張新牌，我們需要插入到適當?shù)奈恢靡员３株犃幸廊挥行颉?/p>
懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。
（所有范例一律從小到大排序）
插入排序的思路可以參考抓撲克牌：假定我們已有的撲克牌已經(jīng)有序，現(xiàn)在抓了一張新牌，我們需要插入到適當?shù)奈恢靡员３株犃幸廊挥行颉?/p>
插入排序
給定數(shù)組：
var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ];
算法描述：
當數(shù)組只有一個元素時，我們認為它有序(廢話)；所以起始從i=1開始，既抓第二張牌后，選擇適當?shù)奈恢?；此時我們將第二張牌與第一張牌比較，由于26比54小，所以將54移動到第二個位置，最后將新牌既26放到首位，此時隊列前兩位有序：
[ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ]
現(xiàn)在i=2，既93與前一張比較，93比54大，所以不需要繼續(xù)向前比較了，保持不動即可；因為前兩位有序，93既然比54大，自然比54之前的任意元素大；此時隊列前3位有序；
[ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ]
現(xiàn)在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步驟，直到整個數(shù)組有序;
第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 ]
算法實現(xiàn):
function insert(list) {
// 數(shù)組第一位有序，從第二位開始
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 ]
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/93391.html
摘要：懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。所有范例一律從小到大排序選擇排序比冒泡的改進是，不會頻繁交換元素，而只是記錄索引，最后再交換。 懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。 （所有范例一律從小到大排序） 選擇排序比冒泡的改進是，不會頻繁交換元素，而只是記錄索引，最后再交換。 選擇排序 給定數(shù)組： var list = [ 54, 26, 93...
懶惰了很久，人有點生銹，所以寫個算法系列讓自己腦筋活躍起來。 （所有范例一律從小到大排序） 冒泡排序 給定數(shù)組： var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ]; 算法描述： 將第一個元素與第二個元素對比，此時第一個元素比第二個元素大，交換他們，這樣較大的元素就位于第二個位置了; list = [ 26, 54, 93, 17, 77...
摘要：代碼實現(xiàn)六堆排序算法簡介堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。九計數(shù)排序算法簡介計數(shù)排序是一種穩(wěn)定的排序算法。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。 贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介 插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...
摘要：二代碼簡單選擇排序一分析循環(huán)次，每一次的當前項與其之后的項作比較，找出其中最小的那個，與當前項交換。二代碼希爾排序是一種改進版的插入排序，縮小增量排序。這樣做的目的是因為，直接插入排序在序列基本有序時效率最高。 排序算法 平均情況 最好情況 最壞情況 輔助空間 穩(wěn)定性 冒泡排序 O(n^2) O(n) O(n^2) O(1) 穩(wěn)定 簡單選擇排序 O(n^2) O(n^2)...
摘要：算法原理插入排序是一種簡單直觀的排序算法。插入排序在實現(xiàn)上，通常采用排序，因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。新元素插入當前位置。 算法原理 插入排序是一種簡單直觀的排序算法。它的工作原理非常類似于我們抓撲克牌。對于未排序的數(shù)據(jù)（右手抓到的牌），在已排序序列（左后已經(jīng)排好序的牌）中從后向前掃描，找到相應位置并插入。插入排序在實現(xiàn)上，通常采...
閱讀 1715·2021-11-02 14:47
閱讀 3661·2019-08-30 15:44
閱讀 1350·2019-08-29 16:42
閱讀 1743·2019-08-26 13:53
閱讀 945·2019-08-26 10:41
閱讀 3476·2019-08-23 17:10
閱讀 615·2019-08-23 14:24
閱讀 1729·2019-08-23 11:59
