JAVA十大排序算法之插入排序详解

目录
  • 插入排序
    • 代码实现
    • 动图演示
    • 代码实现
    • 时间复杂度
    • 算法稳定性
  • 总结

插入排序

当我们在玩扑克牌的时候，总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

1.对于未排序数据（一般取数组的二个元素，把第一个元素当做有序数组），在已排序序列中从左往右扫描，找到相应位置并插入。

2.为了给要插入的元素腾出空间，需要将插入位置之后的已排序元素在都向后移动一位。

代码实现

对下面数组实现排序：{15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}

动图演示

代码实现

public class InsertionSort {
    public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1};
    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        //待排序数据，改数据之前的已被排序
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            //已被排序数据的索引
            int index = i;
            current = array[index + 1];
            //将当前元素后移一位
            while (index >= 0 && current < array[index]) {
                array[index + 1] = array[index];
                index--;
            }
            //插入
            array[index + 1] = current;
        }
        return array;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

在上面图示中，第一趟循环比较一次，第二趟循环两次，依次类推，则最后一趟比较n-1次：

1 + 2 + 3 +… + n-1 = n*(n-1)/2

也就是说，在最坏的情况下（逆序），比较的时间复杂度为O(n2)

在最优的情况下，即while循坏总是假的，只需当前数跟前一个数比较一下就可以了，这时一共需要比较n-1次，时间复杂度为O(n)。

算法稳定性

在比较的时候，过两个数相等的话，不会进行移动，前后两个数的次序不会发生改变，所以插入排序是稳定的。

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • Java 选择排序、插入排序、希尔算法实例详解

    Java 选择排序、插入排序、希尔算法实例详解

    1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu

  • 浅谈Java常见的排序算法

    浅谈Java常见的排序算法

    目录 一.直接插入排序 二. 希尔排序 三.冒泡排序 四.快速排序 五.选择排序(Selection Sort) 六.堆排序 七.归并排序 一.直接插入排序 基本思想: 将一个记录插入到已排序的有序表中,使插入后的表仍然有序 对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序 package Sort; //插入排序 public class InsertSort { public static void main(String[] args) { int [] ar

  • java 排序算法之希尔算法

    java 排序算法之希尔算法

    目录 插入排序存在的问题 简单介绍 基本思想 代码实现 大数据量耗时测试 移动法实现希尔排序 移动法-大数据量耗时测试 算法分析 注:学习本篇的前提是要会插入排序,数据结构与算法--排序算法-插入排序 插入排序存在的问题 简单的插入排序可能存在的问题. 如数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小),过程是: 展示的是要移动 1 这个数,的过程,由于在最后,需要前面的所有数都往后移动一位 {2,3,4,5,6,6} {2,3,4,5,5,6} {2,3,4,4,5,

  • JAVA十大排序算法之插入排序详解

    JAVA十大排序算法之插入排序详解

    目录 插入排序 代码实现 动图演示 代码实现 时间复杂度 算法稳定性 总结 插入排序 当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列. 插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的. 1.对于未排序数据(一般取数组的二个元素,把第一个元素当做有序数组),在已排序序列中从左往右扫描,找到相应位置并插入. 2.为了给要插入的元素腾出空

  • JAVA十大排序算法之归并排序详解

    JAVA十大排序算法之归并排序详解

    目录 归并排序 怎么分 怎么治 代码实现 时间复杂度 算法稳定性 总结 归并排序 归并,指合并,合在一起.归并排序(Merge Sort)是建立在归并操作上的一种排序算法.其主要思想是分而治之.什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总.即"分"就是把一个大的通过递归拆成若干个小的,"治"就是将分后的结果在合在一起. 若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并. 怎么分 对于

  • JAVA十大排序算法之冒泡排序详解

    JAVA十大排序算法之冒泡排序详解

    目录 冒泡排序 代码实现 代码实现 时间复杂度 算法稳定性 总结 冒泡排序 1.从数组头开始,比较相邻的元素.如果第一个比第二个大(小),就交换它们两个 2.对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数 3.重复步骤1~2,重复次数等于数组的长度,直到排序完成 代码实现 对下面数组实现排序:{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9} 代码实现 public class BubbleSort {

  • JAVA十大排序算法之堆排序详解

    JAVA十大排序算法之堆排序详解

    目录 堆排序 知识补充 二叉树 满二叉树 完全二叉树 二叉堆 代码实现 时间复杂度 算法稳定性 思考 总结 堆排序 这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆.它具有以下特点: 它是完全二叉树 堆中某个结点的值总是不大于或不小于其父结点的值 知识补充 二叉树 树中节点的子节点不超过2的有序树 满二叉树 二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树. 完全二叉树 如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右.则深度为k的,有

  • JAVA十大排序算法之基数排序详解

    JAVA十大排序算法之基数排序详解

    目录 基数排序 代码实现 时间复杂度 算法稳定性 基数排序 vs 桶排序 vs 计数排序 总结 基数排序 常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成. 基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,同时每一轮排序都基于上轮排序后的结果:当我们将所有的位排序后,整个数组就达到有序状态.基数排序不是基于比较的算法. 基数是什么意思?对于十进制整数,每一位都只可能是0~9中的某一个,总共10种可能.那10就是它的基,

  • JAVA十大排序算法之快速排序详解

    JAVA十大排序算法之快速排序详解

    目录 快速排序 问题 思路 荷兰国旗问题 代码实现 时间复杂度 算法稳定性 总结 快速排序 快速排序是对冒泡排序的一种改进,也是采用分治法的一个典型的应用.JDK中Arrays的sort()方法,具体的排序细节就是使用快速排序实现的. 从数组中任意选取一个数据(比如数组的第一个数或最后一个数)作为关键数据,我们称为基准数(pivot,或中轴数),然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,也称为分区(partition)操作. 问题 若给定一个无序数组

  • Java 十大排序算法之插入排序刨析

    Java 十大排序算法之插入排序刨析

    目录 插入排序原理 插入排序API设计 插入排序代码实现 插入排序的时间复杂度分析 插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位 插入排序API设计 类名 Insertion 构造方法 Insertion():创建Insertion对象 成员方法 1.public static void sort

  • Java 十大排序算法之希尔排序刨析

    Java 十大排序算法之希尔排序刨析

    目录 希尔排序原理 希尔排序的API设计 希尔排序的代码实现 希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本. 希尔排序原理 1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组. 2.对分好组的每一组数据完成插入排序. 3.减小增长量,最小减为1,重复第二步操作. 希尔排序的API设计 类名 Shell 构造方法 Shell():创建Shell对象 成员方法 1.public static void sort(Comparable

  • Java 十大排序算法之冒泡排序刨析

    Java 十大排序算法之冒泡排序刨析

    目录 冒泡排序原理 冒泡排序API设计 冒泡排序的代码实现 冒泡排序的时间复杂度分析 冒泡排序原理 ①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置 ②对每一对相邻的元素循环上面的步骤,最终最后面的元素就是最大值 冒泡排序API设计 类名 Bubble 构造方法 Bubble:创建Bubble对象 成员方法 1.public static void sort(Comparable[] a):对数组内元素进行排序 2.private static void greater(C

  • Java 十大排序算法之选择排序刨析

    Java 十大排序算法之选择排序刨析

    目录 选择排序原理 选择排序API设计 选择排序代码实现 选择排序的时间复杂度 选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引 ②交换第一个索引处和最小值所在的索引处的值 选择排序API设计 类名 Selection 构造方法 Selection():创建Selection对象 成员方法 1.public static void sort(Comparable[] a):对

随机推荐