一个Java小白通向数据结构算法之旅(6) - 插入排序

前言

过几天就是双11了,现在的我已经没有任何购物的欲望了。也许会在双11,买几本书,充实一下自己,仅此而已。

timg.jpg


插入排序的优点

在一般情况下,插入排序是基本排序算法中最好的一种。虽然插入排序算法需要O(N^2)的时间,但是一般情况下,它要比冒泡排序快一倍,比选择排序还要快一些。

提取思想

  • 我们可以认为插入排序是局部有序。左边是局部有序,右边是无序的。
  • 假如在一串数字中,我们选择了一个标记的数字。在这个作为标记的数字左边的所有数字都已经是局部有序了。这意味着这一部分人之间是按顺序排列的,但是这些数字在队列中的最终的位置还没有确认。因为当没有被排序的数字插入到它们中间的时候,它们的位置还需要发生变化。
  • 我们要在局部有序中的适当位置插入被标记的数字。需要把部分已经排序的数字右移以腾出空间。首先让标记的数字出列,然后将局部有序中最大的数字移动原来被标记的数字所在位置,次大的数字移动原来最大的数字所在的位置,以此类推

手写代码

public class InsertSortDemo {

    public static int[] a = { 11, 20, 5, 4, 8, 14, 2, 10, 20, 9 };

    public static void main(String[] args) {
        // commonInsertSort();
        binaryInsertSort();
        display();
    }

    // 普通插入
    public static void commonInsertSort() {
        int count = a.length;

        for (int i = 0; i < count; i++) {
            int value = a[i];
            int j = i - 1;

            while (j >= 0 && a[j] > value) {
                a[j + 1] = a[j];
                j--;
            }

            a[j + 1] = value;
        }
    }

    // 二分法插入
    public static void binaryInsertSort() {
        int count = a.length;
        int insertValue;

        for (int i = 0; i < count; i++) {
            int start = 0;
            int end = i - 1;
            int mid;
            insertValue = a[i];

            while (start <= end) {
                mid = start + (end - start) / 2;

                if (insertValue > a[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }

            for (int k = i; k > start; k--) {
                a[k] = a[k - 1];
            }

            a[start] = insertValue;
        }
    }

    public static void display() {
        int count = a.length;

        for (int i = 0; i < count; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }
}
  • 这里的插入排序分别为普通的插入排序和二分法插入排序。
  • 打印输出结果。

image.png


插入排序的效率

  • 在第一趟排序中,它最多比较一次,第二趟最多比较2次,以此类推,最后一趟最多,比较N - 1次。因此是 N * (N - 1) / 2。然而在每一趟排序发现插入点之前,平均只有全体数据项的一半进行了比较,我们除以2就是N * (N - 1) / 4
  • 复制的次数大致等于比较的次数。因为一次复制和一次比较的时间耗费不同,所以插入排序相对于冒泡排序快一倍,比选择排序略快。
  • 对于已经有序或者基本有序的数据来说,插入排序要好的多。当数据有序的时候,while循环的条件总为假,所以它变成了外层循环中的一个简单的语句,执行 N - 1次。在这种情况下,算法运行时间只需要O(N)的时间。如果数据基本有序,插入排序几乎只需要O(N)的时间。
  • 对于逆序排列的数据,每次比较和移动都会执行,所以插入排序不比冒泡排序快。

尾言

最近养着了白天睡觉,晚上写代码的习惯,于是乎成了一只特立独行的猪了。生活作息不规律,这是病,该治一治了。还是那一句话,勿以善小而不为。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

理解桶排序算法原理

计数排序,基数排序,桶排序是所有排序算法里面时间复杂度能达到O(N)级别的算法,这主要原因是因为他们不采用基于比较的算法,前面的文章已经介绍了计数排序的原理,本...

67440
来自专栏轮子工厂

快速搞定8大排序算法

11220
来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

197100
来自专栏ACM算法日常

一次看懂进制转换(阶乘是关键) - HDU 2031

对于二进制的转换,我们通常有这样的公式,例如对于一个二进制111001,转换为十进制xx:

21830
来自专栏Java帮帮-微信公众号-技术文章全总结

八大排序算法详解_面试+提升

八大排序算法详解_面试+提升 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排...

40490
来自专栏糊一笑

排序算法总结与实现

写在前面 一直很惧怕算法,总是感觉特别伤脑子,因此至今为止,几种基本的排序算法一直都不是很清楚,更别说时间复杂度、空间复杂度什么的了。 今天抽空理了一下,其实感...

35190
来自专栏数据结构与算法

P3709 大爷的字符串题(50分)

题目背景 在那遥远的西南有一所学校 /*被和谐部分*/ 然后去参加该省省选虐场 然后某蒟蒻不会做,所以也出了一个字符串题: 题目描述 给你一个字符串a,每次询问...

35170
来自专栏目标检测和深度学习

常用排序算法总结(1)

13920
来自专栏钱塘大数据

【推荐收藏】十大经典排序算法(动图演示)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也...

9620
来自专栏顶级程序员

各大排序算法性能比较及演示实例

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

370100

扫码关注云+社区

领取腾讯云代金券