排序算法-插入排序

算法简介

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因为在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

算法描述

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

代码实现

    /**
     * 插入
     *
     * @param array
     */
    private static void insertionSort(int[] array) {
        if (array == null || array.length == 0 || array.length == 1)
            return;
        int insertVal;//插入的元素
        int index;//被插入的位置
        // 默认array[0]是有序的,将剩下的插入到该有序数组中
        for (int i = 1; i < array.length; i++) {
            insertVal = array[i];
            index = i;
            // 如果要插入的元素小于第index-1个元素,就将第index-1个元素向后移动
            while (index > 0 && insertVal < array[index - 1]) {
                array[index] = array[index - 1];
                index--;
            }
            array[index] = insertVal;//放置insertVal
        }
    }

性能分析

最好的情况:正序有序(从小到大),这样只需要比较 n 次,不需要移动。因此时间复杂度为\(O(n)\)。

最坏的情况:逆序有序,这样每一个元素就需要比较 n 次,共有 n 个元素,因此实际复杂度为 \(O(n^2)\)。

平均情况:\(O(n^2)\)。

空间复杂度:\(O(1)\)。

如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

排序算法

平均时间复杂度

最好情况

最坏情况

空间复杂度

稳定性

插入排序

\(O(n^2)\)

\(O(n)\)

\(O(n^2)\)

\(O(1)\)

稳定

插入排序优化(二分法)

二分(折半)插入排序是一种在直接插入排序算法上进行改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式,在速度上有一定提升。

    /**
     * 插入优化(二分法)
     *
     * @param array
     */
    private static void insertionSort_2(int[] array) {
        if (array == null || array.length == 0 || array.length == 1)
            return;
        int insertVal;//插入的元素
        int left;
        int right;
        int middle;
        // 默认array[0]是有序的,将剩下的插入到该有序数组中
        for (int i = 1; i < array.length; i++) {
            insertVal = array[i];
            left = 0;
            right = i - 1;
            while (left <= right) {
                middle = (left + right) >> 1;
                //如果待插入元素比中间元素小
                if (array[middle] > insertVal) {
                    // 插入点在左
                    right = middle - 1;
                } else {
                    // 插入点在右
                    left = middle + 1;
                }
            }
            //将前面所有大于当前待插入元素的元素后移
            for (int j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            }
            //将待插入元素插入到正确位置
            array[left] = insertVal;
        }
    }

性能分析

插入每个元素需要\(O(log n)\)次比较,最多移动 i+1 次,最少 2 次。

最好情况时间复杂度为\(O(n log n)\),最坏和平均情况时间复杂度为\(O(n^2)\)。

二分搜索比顺序搜索查找快,所以二分插入排序就平均性能来说比直接插入排序要快。

当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。

在对象的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列。

二分插入排序是一个稳定的排序方法。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏noteless

[二]基础数据类型之Long详解

toUnsignedString 系列   toString  toXXXString  系列

31430
来自专栏老司机的技术博客

人人都能学会的python编程教程6:列表(list)

当索引超出了范围时,Python会报一个IndexError错误,所以,要确保索引不要越界,记得最后一个元素的索引是len(classmates) - 1。如果...

434100
来自专栏我是攻城师

理解插入排序,希尔排序,选择排序的算法原理

在前面的文章中,其实已经把效率比较高的排序算法给分析过了,比如比较通用的快排,归并排序和堆排,还有用于特定场景的计数排序等。本篇我们把剩下的几种效率一般的排序算...

11310
来自专栏人工智能LeadAI

Python生成器

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

17720
来自专栏ACM算法日常

分割排序(排序)- HDU 1106

输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头,这些头部的‘0’应该被忽略掉,除非这个整...

8710
来自专栏Python攻城狮

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

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

15310
来自专栏尾尾部落

[剑指offer] 链表中倒数第k个结点 [剑指offer] 链表中倒数第k个结点

经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个...

10420
来自专栏HTML5学堂

操作符与数据类型转换

上一期堡堡给大家讲解了关于JS的基础语法,虽然是一些非常基础的知识,但是它对大家的后期学习奠定了一定的基础。知识像一张网,基础越扎实,网住的鱼就越多,要告诉大家...

31880
来自专栏nummy

python堆排序heapq

堆是一种树形数据结构,其中子节点与父节点之间是一种有序关系。最大堆中父节点大于或等于两个子节点,最小堆父节点小于或等于两个子节点。Python的heapq模块实...

28130
来自专栏游戏开发那些事

【Cocos2d-x游戏开发】细数Cocos2d-x开发中那些常用的C++11知识

  自从Cocos2d-x3.0开始,Cocos2dx就正式的使用了C++11标准.C++11简洁方便的特性使程序的可拓展性和可维护性大大提高,也提高了代码的书...

11530

扫码关注云+社区

领取腾讯云代金券