JS实现插入排序

tolerious 发布于2019-08-22 18:31 / 1934人阅读

摘要：但是，插入排序真的一无是处吗答案是否定的，插入排序在实践中的使用频率是很高的，在一些场景下，甚至展现出完胜高级排序的效率。那么插入排序实际上就是每次将一个数插入到有序的数组中去初始一个数字自然有序。

直接插入排序的时间复杂度为 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排序插入排序

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

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