【一起学习排序算法】4 插入排序

栏目: 编程工具 · 发布时间: 5年前

内容简介:先看看Wikipedia的定义:所以插入排序的思路就是:可以通过动画演示理解, 以下网上找的两个动画。如果你想操作不同的参数来演示,可以上这个网站visualgo.net动手试试。

先看看Wikipedia的定义:

Insertion sort algorithm iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

所以插入 排序 的思路就是:

  • 把列表分为两个部分,一部分是已经排好序,一部分待排序。(这一点和选择排序类似)
  • 初始将第一个元素作为有序子列为,然后每次迭代从有序序列中移除;然后将它插入到有序序列中的相应位置。
  • 重复以上步骤,直到到最后一个元素,则表示数组有序。

图示

可以通过动画演示理解, 以下网上找的两个动画。如果你想操作不同的参数来演示,可以上这个网站visualgo.net动手试试。

【一起学习排序算法】4 插入排序
【一起学习排序算法】4 插入排序

代码实现

关于代码,README中代码只有实现算法的函数,具体运行的代码,请查看该目录下的文件。

代码如下:

const insertSort = (array) => {
    // 不修改原数组
    const originValues = array.slice(); 

    // 初始将第一个元素指定为有序子列,从第2个元素开始插入,直到n-1元素 
    for (let i = 1; i < originValues.length; i++) {
        const currentValue = originValues[i];
        // 标记插入有序子列的位置
        let insertIndex = i;
        // 将当前元素从右到左与有序子列元素比较
        // 起始位置为当前元素前一个元素,即i-1,终止位置为0
        // 如果当前元素比该有序子列元素小,则该元素后移一位,并修改插入位置的游标
        for (let j = i-1; j > -1 && currentValue < originValues[j]; j--) {
           originValues[j+1] = originValues[j];
           insertIndex = j;
        }
        // 插入指定位置
        originValues[insertIndex] = currentValue;
    }

    return originValues;
};
复制代码

以上就是直接插入排序的代码实现。总体来说还是比较简单易懂,其实就类似于打扑克,不断将扑克牌按顺序插入指定位置。唯一可能有一点容易想不清楚的,就是有序子列的右移部分。想清楚一点,只要有序子列的该元素大于要插入的元素,该元素就要后移一位。

算法分析

1. 时间复杂度

排序算法中,两个元素的比较次数是影响运行时间的首要因素。所以我们可以通过这个层面来评估。

最优复杂度

当数组有序时,每一次迭代只有一次比较,所以总共有n-1次比较,复杂度为O(n)。

最差复杂度

当数组逆序时,每一次都要比较整个有序子列,比较次数为:

T(n) = 1 + 2 + ... + n-1 = n*n/2
复制代码

所以,最差复杂度是O(n 2 )。

2. 稳定性

因为比较元素是,相同值不会交换,所以插入算法是稳定的。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

疯传:让你的产品、思想、行为像病毒一样入侵(全新修订版)

疯传:让你的产品、思想、行为像病毒一样入侵(全新修订版)

[美] 乔纳•伯杰(Jonah Berger) / 乔迪、王晋 / 电子工业出版社 / 2016-6 / 68.00

是什么让事物变得流行? 从买轿车、买衣服、吃三明治,到给孩子取名字,你是否知道为什么某些产品会大卖,某些故事被人们口口相传,某些电子邮件更易被转发,或者某些视频链接被疯狂地点击,某些谣言更具传播力,某些思想和行为像病毒一样入侵你的大脑……这本书将为你揭示这些口口相传和社会传播背后的科学秘密,并且告诉你如何将产品、思想、行为设计成具有感染力和传播力的内容。 无论你是大公司的管理者,还是努......一起来看看 《疯传:让你的产品、思想、行为像病毒一样入侵(全新修订版)》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

在线进制转换器
在线进制转换器

各进制数互转换器

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码