普林斯顿大学算法公开课笔记——插入排序

插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。——极客学院

算法描述

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤 2~5

复杂度分析

  1. 时间复杂度:1/4 N^2的交换次数和比较次数
    • 在最坏情况下,数组完全逆序,插入第2个元素时要考察前1个元素,插入第3个元素时,要考虑前2个元素,……,插入第N个元素,要考虑前 N – 1 个元素。因此,最坏情况下的比较次数是 1 + 2 + 3 + … + (N – 1),等差数列求和,结果为 N^2 / 2,所以最坏情况下的复杂度为 O(N^2)。
    • 最好情况下,数组已经是有序的,每插入一个元素,只需要考查前一个元素,因此最好情况下,时间是线性的,时间复杂度为O(N)。
    • 插入排序的速度大约是选择排序的两倍 > 排序算法的稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。
  2. 空间复杂度分析 算法所需的辅助空间是一个监视哨,辅助空间复杂度 S(n)=O(1)。是一个就地排序。
  3. 直接插入排序的稳定性 直接插入排序是稳定的排序方法。

实例分析

现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下:

[5]   6   3   1   8   7   2   4
  ↑   │
  └───┘
[5, 6]   3   1   8   7   2   4
↑        │
└────────┘
[3, 5, 6]  1   8   7   2   4
↑          │
└──────────┘
[1, 3, 5, 6]  8   7   2   4
           ↑  │
           └──┘
[1, 3, 5, 6, 8]  7   2   4
            ↑    │
            └────┘
[1, 3, 5, 6, 7, 8]  2   4
   ↑                │
   └────────────────┘
[1, 2, 3, 5, 6, 7, 8]  4
         ↑             │
         └─────────────┘

[1, 2, 3, 4, 5, 6, 7, 8]

源代码

public class Insertion
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for(int i=1; i<N; i++)
            for(int j=i; j>0;j--)
                if(less(a[j],a[j-1]))
                    exch(a,j,j-1)
                else break;
    }
    private static boolean less(Comparable v, Comparable w)
    {
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a, int i, int j)
    {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}
参考文献

常见排序算法 – 插入排序 (Insertion Sort) 直接插入排序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武军超python专栏

2018年8月23日python中列表的高级操作:列表推导式,列表生成器,列表迭代器

列表在我们平常的编程中经常会用到,多用于临时存储一些程序需要的数据, 向列表中添加数据时,有多种方式: 1.数据少的话直接定义列表中的数据 my1 = [...

1583
来自专栏海天一树

图的深度优先搜索

图有两种最基本的搜索算法,一种是深度优先搜索,另一种是广度优先搜索。本节先介绍深度优先搜索。

932
来自专栏积累沉淀

必须掌握的八种排序(7-8)--归并排序,基数排序

7、归并排序 (1)基本排序:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后...

2285
来自专栏Android开发指南

2 :基本语法

36111
来自专栏编程

python学习第二天:python的函数、循环和条件、类

第一天学习了Python的基本操作,以及几种主要的容器类型,今天学习 ,这样才算对Python有一个大致的了解。今天的学习大纲如下: 三、函数 1、定义函数 四...

1796
来自专栏Python爱好者

Java基础笔记05

1598
来自专栏大闲人柴毛毛

剑指offer——面试题10输入一个十进制整数,统计其中二进制1的个数

/** * 题目:输入一个十进制整数,统计其中二进制1的个数 * @author 大闲人柴毛毛 */ public class CountBitOne {...

3644
来自专栏C/C++基础

数组的全排列

学过数学的人都知道,全排列的意思是什么。现在如何用计算机的编程语言实现数组的全排列呢?

1921
来自专栏Python攻城狮

Python-生成器1.什么是生成器2.创建生成器方法 3.send 4.实现多任务 5.迭代器 6.闭包

通过列表生成式,我们可以直接创建一个列表。但是,受到内存限制,列表容量肯定是有限的。而且,创建一个包含100万个元素的列表,不仅占用很大的存储空间,如果我们仅仅...

1351
来自专栏Python疯子

数据分析之numpy

ndarray概述 创建n维数组 接收的是列表类型,所有元素类型必须相同 shape表示各维度大小的元组 dtype表示数组数据类型对象

1481

扫码关注云+社区

领取腾讯云代金券