Java数据结构与算法——插入排序

骞讳护发布于2019-08-15 15:19 / 1940人阅读

摘要：当序列本身有序时，插入排序的时间复杂度为。因为此时的分区内数据往往是近似有序的，所以使用快排并不一定优于插入排序。

声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。

前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇文章介绍排序算法中插入排序算法，包括插入排序的思路，适用场景，性能分析，java代码等

0、其他排序算法索引(待更)

java数据结构与算法——快速排序
java数据结构与算法——桶排序

1、插入排序的思想及原理

插入排序一般分为直接插入排序和二分插入排序，本文只介绍直接插入排序，两者的区别仅在于插入的方式不一样。

插入排序是在待排序数组里插入数据。一般我们认为插入排序就是往一个已经排好序的数列中插入一个元素，使得插入这个数以后，数组仍然有序。

下面具体介绍下插入排序的思路：

首先需要明确待排序的数组由两部分组成，一部分是已经排好序的部分，另一部分是待排序的部分。

接着我们每次选取待排序部分的第一个元素，分别与前面排好序的元素进行比较。当大于前面元素时，可以将该元素直接进入已排好序的部分；当小于前面元素时，需要把这个元素拿出来暂存，将前面的元素后移，继续与前面的元素相比，直到比较到数组第一个元素或者出现第一个小于拿出的这个元素，这时停止比较、移动，直接把这个元素放到当前空位上。

一直重复步骤2，直到待排元素已经没有元素可进行插入时，停止操作，当前数列为已排好序的数列。

2、插入排序java代码实现

首先最外层必定有个大循环，用于待排序部分的数列。还需要一个内层循环，分别与前面排好序的部分进行比较和移动，直到找到位置可以进行插入。参照扑克牌摸牌后排序

public class InsertSort {
    private int[] array;
    public InsertSort(int[] array){
        this.array = array;
    }
    
    public void insertSort(){
        if(array==null){
            throw new RuntimeException("没有待排数组");
        }
        int length = array.length;
        if(length>0){
            for(int i=1;i0&&array[j-1]>temp;j--){  //原理中的步骤2
                    array[j] = array[j-1];   //移位
                }
                array[j] = temp;   //插入
            }
        }
    }
    
    public void print(){  //用于打印排完序后的数组
        for(int i=0;i
测试程序
public class SortTest {
    public static void main(String[] args) {
        insertSortTest();
    }

    private static void insertSortTest(){
        int[] array = {3,5,0,7,1,4,6};
        InsertSort is = new InsertSort(array);
        is.insertSort();
        is.print();
    }
}
3、插入排序的特点及性能
插入排序和玩扑克牌摸牌后在手中排序一样的原理，比较容易理解。插入排序在序列近似有序时，效率比较高，因为此时减少了比较和移动的次数。
从原理和代码来看，插入排序的时间复杂度尾O(n^2)，外层循环执行n次，内层在最坏的情况下也执行n次，并且除了比较操作还有移动操作。最好的情况是序列近似有序，这时内层循环只需比较及移动较少个元素即可完成。当序列本身有序时，插入排序的时间复杂度为O(n)。因此，在数列越有序，效率越高。
空间复杂度为O(1)，是常量级的。因为只用了一个变量暂存每次未排好序的首个元素。
插入排序是稳定的排序算法，因为是在相对排好序的基础上进行比较和移动，所以可以保持相对顺序不变，所以是稳定的排序算法。
4、插入排序的适用场景
插入排序的特点是在近似有序的情况下效率比较高。但因为其时间复杂度为O(n^2)，所以通常并不多带带适用。在所有的排序算法中，我们优先使用快速排序。快速排序在分区规模达到一定的值时（比如10左右），我们改用插入排序算法排该分区。因为此时的分区内数据往往是近似有序的，所以使用快排并不一定优于插入排序。在很多高级语言在内部对快速排序的实现中，也是在分区达到一定规模改用插入排序来排该分区。
其他排序算法索引(待更)
java数据结构与算法——快速排序
java数据结构与算法——桶排序
码字不易，如对您有帮助，欢迎点赞收藏打赏^_^

GPU云服务器云服务器 java插入排序算法插入排序算法 java插入排序优化插入排序java

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

转载请注明本文地址：https://www.ucloud.cn/yun/68993.html

数据结构与算法——常用排序算法及其Java实现

摘要：数据结构与算法常用数据结构及其实现经过前面文章的铺垫，我们巩固了基础数据结构的知识，接下来就可以进入算法的巩固阶段了。首先我们来看常见的排序算法。同样的小规模数据转换为插入排序会有效果提升。它只能对整数进行排序。数据结构与算法——常用数据结构及其Java实现经过前面文章的铺垫，我们巩固了基础数据结构的知识，接下来就可以进入算法的巩固阶段了。首先我们来看常见的排序算法。冒泡排序原理...

eternalshallow 2019-08-15 13:48 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segm...

GeekQiaQia 2019-08-21 11:41 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segm...

cgspine 2019-08-16 10:33 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segm...

lufficc 2019-07-31 10:56 评论0 收藏0
八大排序算法Java实现

摘要：向后移动位简单选择排序基本思想常用于取序列中最大最小的几个数时。代码实现循环次数选出最小的值和位置交换位置堆排序基本思想对简单选择排序的优化。概述常见的八大排序算法，它们之间的关系如下： showImg(https://segmentfault.com/img/remote/1460000011395738?w=880&h=671); 直接插入排序希尔排序简单选择排序堆排序...

Coly 2019-08-15 11:57 评论0 收藏0