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

Guakin_Huang 发布于2019-08-22 15:20 / 657人阅读

摘要：懒惰了很久，人有点生锈，所以写个算法系列让自己脑筋活跃起来。所有范例一律从小到大排序插入排序的思路可以参考抓扑克牌假定我们已有的扑克牌已经有序，现在抓了一张新牌，我们需要插入到适当的位置以保持队列依然有序。

懒惰了很久，人有点生锈，所以写个算法系列让自己脑筋活跃起来。

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

插入排序的思路可以参考抓扑克牌：假定我们已有的扑克牌已经有序，现在抓了一张新牌，我们需要插入到适当的位置以保持队列依然有序。

插入排序

给定数组：

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插入排序算法插入排序实现插入排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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