【排序算法动画解】直接插入排序

22
• 阅读 1859

本文为系列专题【数据结构和算法:简单方法】的第 14 篇文章。

  1. 数据结构 | 顺序表
  2. 数据结构 | 链表
  3. 数据结构 | 栈
  4. 数据结构 | 队列
  5. 数据结构 | 双链表和循环链表
  6. 数据结构 | 二叉树的概念和原理
  7. 数据结构 | 二叉树的创建及遍历实现
  8. 数据结构 | 线索二叉树
  9. 数据结构 | 二叉堆
  10. 算法 | 顺序查找和二分查找
  11. 数据结构(视频) | 二叉查找树
  12. 排序算法(视频) | 排序基本介绍和冒泡排序
  13. 排序算法(视频) | 简单选择排序

前面介绍了已经介绍了三种排序,暴力排序、冒泡排序和简单选择排序,一个共同点都是基于交换。

我们可以用另一种视角来看待排序,即将一个待排序的数组看成两个部分:有序区乱序区

在排序开始前,整个数组都是乱序区,而有序区则为空:

【排序算法动画解】直接插入排序

排序开始后,有序区逐渐扩大,乱序区逐渐缩小:

【排序算法动画解】直接插入排序

排序完成后,整个数组都是有序区,乱序区则为空:

【排序算法动画解】直接插入排序

核心思想:将数组看作无序区和有序区两个区,从无序区中选出一个元素,按大小插入到有序区的合适位置。当无序区为空时,有序区自然就完成排序了。

动态过程如下:

【排序算法动画解】直接插入排序

代码实现如下:

/*
 * 直接插入排序
 * array : 数组
 * length : 数组长度 
 */
void straight_insertion_sort(int *array, int length)
{
    int i, j;
    // 外层循环 决定待插入值
    for (i = 1; i < length; i++) {
        if (array[i] < array[i - 1]) {
            int tmp = array[i]; // 待插入值
            // 内层循环 在有序区中为待插入值腾出位置
            for (j = i - 1; j >= 0 && array[j] > tmp; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = tmp; // 插入
        }
    }
}

请注意插入元素到有序区的关键代码 array[j + 1] = tmp;中的 j+1

以上就是直接插入排序的基本原理。

完整代码请移步至 GitHub | Gitee 获取。

如有错误,还请指正。

如果觉得写的不错,可以点个赞和关注。后续会有更多数据结构和算法相关文章。

微信扫描下方二维码,一起学习更多计算机基础知识。

【排序算法动画解】直接插入排序

点赞
收藏
评论区
推荐文章
22 22
3年前
【排序算法动画解】排序介绍及冒泡排序
本文为系列专题的第12篇文章。1.2.3.4.5.6.7.8.9.10.11.本文先简单介绍一下什么是排序,然后再结合动画介绍暴力排序和冒泡排序。1.什么是排序?排序在日常生活中无处不在。比如考试成绩的排名、体育课的从低到高的队形、网购时按价格升序排列或降序排列等等。|姓名|学号|班级|成绩|||||
22 22
3年前
【排序算法动画解】简单选择排序
本文为系列专题的第13篇文章。1.2.3.4.5.6.7.8.9.10.11.12.在文章【】中,我们介绍了暴力排序和冒泡排序这两种排序算法,算是一个引子。同时指出暴力排序和冒泡排序的缺点硬伤。本文介绍的简单选择排序则“医治”了上面提到的暴力排序和冒泡排序的“硬伤”。核心思想:从数组的第一个元素开始,将其作为基准元素,然后找出基准
Wesley13 Wesley13
3年前
java中几种排序的实现
1.最简单的冒泡排序/\\\冒泡排序\/publicstaticvoidbubbleSort(){int\\arr{5,8,1,2,9,8,7,4};System.out.println("排序前的数组为:");for(intnum:arr){System.o
徐小夕 徐小夕
3年前
程序员必备的几种常见排序算法和搜索算法总结
前言最近为了巩固一下自己的算法基础,又把算法书里的基本算法刷了一遍,特地总结一下前端工程师需要了解的排序算法和搜索算法知识,虽然还有很多高深算法需要了解,但是基础还是要好好巩固一下的.本文将以图文的形式为大家介绍如下算法知识,希望在读完之后大家能有所收获:冒泡排序及其优化选择排序插入排序归并排序快速排序顺序搜索二分搜索
Wesley13 Wesley13
3年前
PHP算法:冒泡排序与快速排序
写一个排序算法,可以是冒泡排序或者快速排序,假设待排序对象是一个二维数组。(提示:不能使用系统已有函数,另外请仔细回忆以前学习过的基础知识)//冒泡排序<brfunctionbubble_sort($array)
{
&nbsp;&nbsp;<br$countcount($array);
&nbsp;&nb
Wesley13 Wesley13
3年前
Java面试总结(排序算法)
1.冒泡排序算法描述:两两比较,大的放后面2.选择排序算法描述:在m元数组中找到最小值的位置,然后将最小值的位置和第n(n0,1,2,....m1)位的值对调,排序k次则m元数组中前k(k<m)位的值已经排序好,m元数组中前k位的值不需要再进行排序,此时需要排序的元素只有mk个3.插入排序算
Wesley13 Wesley13
3年前
C++经典算法题
41.AlgorithmGossip:基数排序法说明在之前所介绍过的排序方法,都是属于「比较性」的排序法,也就是每次排序时,都是比较整个键值的大小以进行排序。这边所要介绍的「基数排序法」(radixsort)则是属于「分配式排序」(distributionsort),基数排序
Stella981 Stella981
3年前
Lua 排序算法
冒泡排序(BubbleSort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。算法步骤1.有一个长度为n
菜园前端 菜园前端
1年前
什么是选择排序?
原文链接:什么是选择排序(selectSort)?选择排序就是在一个排列中划分为有序区和无序区,有序区在左边,无序区在右边。首先在无序区中找到最小元素,存放到有序区的起始位置,然后再从剩余的无序区中继续寻找最小元素,然后放到有序区的末尾。以此类推,直到无序
菜园前端 菜园前端
1年前
什么是插入排序?
原文链接:什么是插入排序(insertionSort)?在数组中从左到右依次取一个数出来,然后把它放到合适的位置。从思想上可以分为有序区和无序区,有序区在左边代表已经排列好的元素。算法步骤1.默认左边第一个元素已经在有序区了2.在无序区取一个数出来(第二个