算法之插入排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法之插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2356字，纯文字阅读大概需要4分钟。

内容图文

插入排序

插入排序也是一个很常见的排序，大家很多都以扑克牌作为例子，非常的形象。我们打牌的时候，
从第一张牌开始，它就是有序的；
第二张牌我们排序后放到第一张的左侧或者右侧；
每来一张牌就都会排序好，直至所有的牌

插入排序的实现流程

1.外循环N-1次，从第一张牌开始就是有序的，从i=1开始外循环
2.内循环从第i张牌开始，保证i张牌加入是有序的，i张牌递减比较
3.每一次插入都保证了前面的数组是有序的

代码实现

package com.java.arlgorithm.sort;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * @author
 */
@Slf4j
public class InsertSortTest {
    public static void main(String[] args) {
        int[] array = new int[]{5, 6, 4, 3, 1, 6};
        //int[] arrayOptmize = new int[]{1, 2, 3, 4, 5, 6};

        inserSort(array);
    }

    public static void inserSort(int[] array) {
        int len = array.length;
        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0 && less(array[j], array[j - 1]); j--) {
                swap(array, j, j - 1);
            }
            printAll(array);
        }
    }

    public static void swap(int[] array, int src, int des) {
        int tmp;
        tmp = array[src];
        array[src] = array[des];
        array[des] = tmp;
    }

    public static boolean less(int a, int b) {
        if (a < b) {
            return true;
        }
        return false;
    }
    public static void printAll(int[] array) {
        log.info(Arrays.toString(array));
    }
}

结果

2019-08-20 14:47:37,146   [main] INFO  InsertSortTest  - [5, 6, 4, 3, 1, 6]
2019-08-20 14:47:37,149   [main] INFO  InsertSortTest  - [4, 5, 6, 3, 1, 6]
2019-08-20 14:47:37,149   [main] INFO  InsertSortTest  - [3, 4, 5, 6, 1, 6]
2019-08-20 14:47:37,149   [main] INFO  InsertSortTest  - [1, 3, 4, 5, 6, 6]
2019-08-20 14:47:37,149   [main] INFO  InsertSortTest  - [1, 3, 4, 5, 6, 6]

时间复杂度

最坏的就是反序导致的判断和交换次数是N的平方，
最好的情况就是N-1次，正序比较，也就是说越是有序越好排列

基本操作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O(f(n))

空间复杂度

插入排序的时间复杂度就是1

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

算法的稳定性

算法根据稳定性的定义是稳定的。

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内容总结

以上是互联网集市为您收集整理的算法之插入排序全部内容，希望文章能够帮你解决算法之插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---