当前位置： 移动技术网 > IT编程>开发语言>Java > 数据结构和算法 - 插入排序

数据结构和算法 - 插入排序

2020年07月31日  | 移动技术网IT编程  | 我要评论

基本介绍

把 n 个待排序的元素看成一个有序表和一个无序表，开始时有序表只有一个值，无序表有 n-1 个值，每次排序从无序表取出元素与有序表进行比对，插入适当位置成为新的有序表。

核心思想

把 n 个待排序的元素看成一个有序表和一个无序表，从无序列表取数据与有序列表对比并插入合适的位置

时间复杂度

排序法 平均时间 最差情形 稳定度 额外空间 备注
插入 O(n2n^{2}) O(n2n^{2}) 稳定 O(1) 大部分排好序时较好

动画演示

在这里插入图片描述

代码思路

使用 for 循环变量 i 作为待插元素，j = i-1 作为有序列表最后一个值，while 循环比较 arr[i] 和 arr[j]的值，若 arr[j] 比待插元素大，则把 arr[j] 的值后移动一位，j - -，最后，待插元素= arr[j+1]

代码实现

/**
 * @author tianhuiwen
 * @date 2020/7/16 17:32
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] array = {3, 9, -10, 5, 10, 20, 6};
        insertionSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void insertionSort(int[] array) {
        int insertNum;
        for (int i = 1; i < array.length; i++) {
            insertNum = array[i];
            int j = i - 1;
            while (j >= 0 && insertNum < array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = insertNum;
        }
    }
}

本文地址：https://blog.csdn.net/thwsir/article/details/107695635

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网