直接插入排序

mgckid 发布于2019-08-14 15:11 / 828人阅读

摘要：插入排序在实现上，通常采用排序即只需用到的额外空间，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。两个相同的保持他们原来的前后顺序，所以直接插入排序是稳定的。

概述

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

换句话说，就是：

假设在序号 i 之前的元素即 [0... i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 位置对应的元素值赋为 x ，插入排序的时间复杂度和空间复杂度分别为 O(n²) 和 O(1)。

步骤

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素（已排序）大于新元素，将该元素移到下一位置

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置中

重复步骤2，直到排好序为止

实例

举个简单的例子，帮助理解。

原始数据：

3 5 2 6 2

第一轮，把 3 作为已经排好序的，取出 5 与 3 进行比较，5 大于 3 位置保持不变，新的有序组为 [3 5]

3 5 2 6 2

第二轮，取出第一个 2 ，从已排序的 [3 5] 数组从后往前比较，与 5 比较，小于 5，将 5 向后移动一个位置，再与 3 比较，小于 3，将 3 向后移动一个位置，前面没有了，将 2 放置在原来 3 的位置，新的有序组为 [2 3 5]

2 3 5 6 2

第三轮，取出 6 ，与 5 比较，5 保持不动，新的有序组 [2 3 5 6]

2 3 5 6 2

第四轮，取出 2 ，与 6 比较，6 向后移动一位，与 5 比较，5 向后移动一位，与 3 比较，3 向后移动一位，与 2 比较，不需移动，将取出的 2 放到原来 3 的位置即可，至此完成排序。

2 2 3 5 6

两个相同的 2 保持他们原来的前后顺序，所以直接插入排序是稳定的。

代码实现(Java)

package com.coder4j.main.arithmetic.sorting;
    
public class StraightInsertion {

    /**
     * 直接插入排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        // 将第一个i=0作为已排序组
        for (int i = 1; i < array.length; i++) {
            System.out.println("第" + i + "轮比较结果：");
            
            // 取出i索引待排序元素
            int temp = array[i];
            int j;
            // 从已排序数组后面往前逐个比较，确定i元素的位置，并将相应的元素后移一位
            for (j = i - 1; j >= 0 && temp < array[j]; j--) {
                array[j + 1] = array[j];
            }
            // 找到了位置
            array[j + 1] = temp;
            // 输出此轮排序结果
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

测试输出结果：

第1轮比较结果：
3 5 2 6 2 
第2轮比较结果：
2 3 5 6 2 
第3轮比较结果：
2 3 5 6 2 
第4轮比较结果：
2 2 3 5 6 
最终结果
2 2 3 5 6

经测试，与实例中结果一致。

GPU云服务器云服务器直接插入排序 php 实现直接插入直接选择排序插入排序

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

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

【算法】插入排序——希尔排序+直接插入排序

希尔排序在介绍希尔排序之前，先了解一下直接插入排序文章目录希尔排序一、直接插入排序1. 单趟排序2. 直接插入排序二、希尔排序三、测试希尔排序和直接插入排序性能一、直接插入排序 1. 单趟排序 x插入一个有序区间这里end是指向数组最后一个元素 2. 直接插入排序根据上面的单趟排序启发 end是数组的最后一个元素，end之后的元素都是待排序一个关键的判断点，end和...

GitChat 2021-11-17 09:33 评论0 收藏0
JS中可能用得到的全部的排序算法

本篇有7k+字, 系统梳理了js中常见的12种排序算法。除了基本排序算法，文章还包含了希尔排序、堆排序、桶排序等较为复杂的排序实现，如果喜欢请点赞支持~谢谢. 原文: http://louiszhai.github.io/20... 导读排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃的(啥是快排, 我只知道...

verano 2019-08-20 15:08 评论0 收藏0
排序（2）：直接插入排序

摘要：一前言直接插入排序序是一种最简单的插入排序。所以，数据越接近正序，直接插入排序的算法性能越好。算法稳定性直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。一、前言直接插入排序（Insertion Sort）序是一种最简单的插入排序。为简化问题，我们下面只讨论升序排序。二、算法思想插入排序：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，...

付伦 2019-07-31 10:08 评论0 收藏0
【数据结构初阶】第九篇——八大经典排序算法总结（图解+动图演示+代码实现+八大排序比较）

摘要：本篇博客我要来和大家一起聊一聊数据结构初阶中的最后一篇博客八大经典排序算法的总结，其中会介绍他们的原来，还有复杂度的分析以及各种优化。快速排序递归版本快速排序是于年提出的一种二叉树结构的交换排序方法。 ...

xiaowugui666 2021-11-25 09:43 评论0 收藏0
Java数据结构与算法——插入排序

摘要：当序列本身有序时，插入排序的时间复杂度为。因为此时的分区内数据往往是近似有序的，所以使用快排并不一定优于插入排序。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇文章介绍排序算法中插入排序算法，包括插入排序的思路，适用场景，性能分析，java代码等 0、其他排序算法索引(待更) java数据结构与算法——快速...

骞讳护 2019-08-15 15:19 评论0 收藏0