直接插入排序

作者: 利伊奥克儿 | 来源:发表于2017-08-28 16:45 被阅读33次

直接插入排序:

什么是直接插入排序?

每一趟将一个待排序的记录,按照其关键字的大小插入到有序队列的合适位置里,直到全部插入完成。

通俗解释一波:

打牌为例:

先拿一张5在手里,

再摸到一张4,比5小,插到5前面,

摸到一张6,嗯,比5大,插到5后面,

摸到一张8,比6大,插到6后面,

。。。

嗯,等你最后一张牌插完,你发现所有牌都有顺序了(这个只对按顺序插牌的同学有效~~~~)

图片解释一波:

代码基本思路:

待排序记录 R1,R2,… ,Rn–1, Rn

第一步:R1

第二步:(R1 ), R2

第三步:(R1 , R2), R3

……

第 j 步:(R1,R2,… ,Rj–1), Rj

……

第 n 步: (R1,R2,… ,Rn–1), Rn.

例:j=5

原有序表中关键词比Rj大的记录数:dj

比较次数:dj+1 移动次数: dj+2

Java代码实现:

public class SortTest {

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] sort = { 4, 5, 6, 7, 9 };

insertSort(sort);

}

public static void insertSort(int[] list) {

// 第1个数肯定是有序的,从第2个数开始遍历,依次插入有序序列

for (int i = 1; i < list.length; i++) {

int j = 0;

int temp = list[i]; // 取出第i个数,和前i-1个数比较后,插入合适位置

// 因为前i-1个数都是从小到大的有序序列,所以只要当前比较的数(list[j])比temp大,就把这个数后移一位

for (j = i - 1; j >= 0 && temp < list[j]; j--) {

list[j + 1] = list[j];

}

list[j + 1] = temp;

}

//处处排序后的结果

for (int i : list) {

System.out.println(i);

}

}

}

输入序列:

sort = { 4, 3, 6, 1, 9 };

输出结果:

1

3

4

6

9

算法性能分析:

时间复杂度:

当数据正序时,执行效率最好,每次插入都不用移动前面的元素,时间复杂度为O(N)

当数据反序时,执行效率最差,每次插入都要前面的元素后移,时间复杂度为O(N2)

所以,数据越接近正序,直接插入排序的算法性能越好

空间复杂度:

由直接插入排序算法可知,我们在排序过程中,需要一个临时变量存储要插入的值,所以空间复杂度为1

算法稳定性:

直接插入排序的过程中,不需要改变相等数值元素的位置,所以它是稳定的算法。

相关文章

  • 插入排序

    一、直接插入排序 二、折半插入排序

  • 【数据结构】【C#】013-插入类排序:🥇直接插入排序(稳定)

    插入排序:直接插入排序(稳定) 【 算法思想 】 直接插入排序是一种最基本的插入排序方法,其基本操作是将第 i 个...

  • 排序——插入排序

    业精于勤荒于嬉 插入排序包括:直接插入排序、折半插入排序、希尔排序(缩小增量排序) 一、直接插入排序 1. 算法思...

  • 常用算法

    插入排序 包括直接插入排序和希尔插入排序 直接插入排序 将一个记录插入到已经排序好的有序表中。 sorted数组的...

  • 算法(排序)

    一、内部排序 1、插入排序—直接插入排序(Straight Insertion Sort) 2、插入排序—希尔排序...

  • 直接插入排序

    //直接插入排序

  • iOS算法

    排序方法 选择排序:直接选择排序、堆排序。 交换排序:冒泡排序、快速排序。 插入排序:直接插入排序、二分法插入排序...

  • 几种实用的简易的排序算法

    也是面试题 一、插入排序 1.插入排序—直接插入排序(Straight Insertion Sort) 思路 遍历...

  • 2.1-插入排序-直接插入

    参考链接 插入排序:直接插入排序(Straight Insertion Sort) 白话经典算法系列之二 直接插入...

  • 经典排序算法-希尔排序Shell sort

    一、希尔排序思想 希尔排序是基于插入排序的快速的排序算法,先分组后对每组进行直接插入排序,再分组再直接执行插入排序...

网友评论

    本文标题:直接插入排序

    本文链接:https://www.haomeiwen.com/subject/skjgdxtx.html