算法学习笔记之插入排序算法

谁践踏了优雅 2022-08-21 07:56 167阅读 0赞

接下我们介绍下一种排序算法：

## 插入排序 ##

插入排序算法通过比较和插入来实现排序，其排序流程如下：  
1）首先对数组前两个数据进行从小到大排序  
2）接下来将第3个数据与排好序的两个数据进行比较，将第3个数据插入合适的位置  
3）然后，将第4个数据插入到排好序的3个数据中  
4）直到最后一个数据插入到排好序的前n-1个数据中即排好序了  
如图：  
![这里写图片描述][20160424080211427]

这里就不解释了，大家应该都看得懂。（**第一次前2个数据排，第二次第3个数据插到前两个中，其实就是找位置**）  
代码：

public static void insertSort(int a[]) {
            for (int i = 1; i < a.length; i++) {
                int t = a[i];
                int j = i - 1;
                while (j >= 0 && t < a[j]) {
                    a[j+1] = a[j];
                    j --;
                }
                a[j+1] = t;
                //输出每次排序的结果
                System.out.printf("第" + i + "次的排序结果为:");
                for (int i2 = 0; i2 < a.length; i2++) {
                    System.out.printf(a[i2] + " ");
                }
                System.out.println();
            }
        }

结果：  
![这里写图片描述][20160424080608197]

时间复杂度：O(N^2)，和其他排序算法的比较请见《算法学习笔记之冒泡排序算法》中的排序算法的比较表。

[20160424080211427]: /images/20220724/a20e0a8e41214032aa29c305b9c7be52.png
[20160424080608197]: /images/20220724/1ff40b2084af45b1af378a063f98b9ce.png

发表评论取消回复

表情：

评论列表（有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法之插入排序

\[插入排序-普通插入排序\] 1.算法思想将元素a视为基序列，遍历数组将元素a右边的元素依次插入序列中，找到比自己小的数置于其后，保证序列一直处于已排序的状态

落日映苍穹つ/ 2022年12月29日 15:28/ 0 赞/ 162 阅读

相关 java插入排序算法_排序算法之 Java插入排序算法

package net.qh.test.sort; import java.util.ArrayList; import java.util.Calendar; impo

本是古典何须时尚/ 2022年11月03日 10:36/ 0 赞/ 183 阅读

相关排序算法之插入排序

同样的先上这张图 ![Center][] 下面分析插入排序：插入排序每次取一个元素插入到已排好序的序列中。由于前面的序列已经排好序，我们只需要从这个序列的后面

待我称王封你为后i/ 2022年09月25日 15:23/ 0 赞/ 191 阅读

相关算法导论学习之插入排序

《算法导论》买了好久了，基本上没怎么看，最近思想上有了转变，觉得学习才是王道。准备重新拾起来学习，下面我就《算法导论》中的排序算法中的插入排序做了个c++的简单实现，附加解

今天药忘吃喽~/ 2022年08月25日 10:53/ 0 赞/ 138 阅读

相关算法学习笔记之插入排序算法

接下我们介绍下一种排序算法：插入排序插入排序算法通过比较和插入来实现排序，其排序流程如下： 1）首先对数组前两个数据进行从小到大排序 2）接下来将第3个数据

谁践踏了优雅/ 2022年08月21日 07:56/ 0 赞/ 168 阅读

相关算法学习笔记之选择排序算法

接下来我们学习第二种排序算法：选择排序 -------------------- 选择排序算法通过选择和交换来排序，其排序流程如下： 1）首先从原始数组中选择最

素颜马尾好姑娘i/ 2022年08月21日 07:56/ 0 赞/ 135 阅读

相关算法学习笔记之冒泡排序算法

我们这里先介绍几种适用的比较少的数据时候，算法复杂度都是O(n2),介绍三种算法： ①冒泡排序算法 ②选择排序算法 ③插入排序算法这篇介绍第一种：冒泡排序算法

迷南。/ 2022年08月21日 07:49/ 0 赞/ 227 阅读

相关排序算法之插入排序

插入排序> 对于排序相信大家都不陌生，就是将一组数据按照从大到小(降序)或者是从小到大(升序)进行排列，那仫常见的排序算法有哪些呢？我总结了以下几种常见的排序算法，在本篇文

冷不防/ 2022年07月15日 12:38/ 0 赞/ 174 阅读

相关排序算法之插入排序

问题描述：输入一个原始数列，把它进行升序排序，从小到大输出。例如：给定数列如下： 5 15 99 45 12 1 90 19 33 41 排序后的结果为： 1

待我称王封你为后i/ 2022年06月16日 07:48/ 0 赞/ 217 阅读

相关 Java-排序算法之插入排序算法

插入排序算法通过对未排序的数据执行逐个插入至合适的位置而完成排序操作。插入排序算法通过比较和插入来实现排序，其排序流程如下： 1、首先对数组的前两个数据进行从小到大的

妖狐艹你老母/ 2022年06月07日 02:18/ 0 赞/ 179 阅读