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

2021/7/12 11:05:53

本文主要是介绍【排序算法动画解】直接插入排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

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

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

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

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

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

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

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

动态过程如下:

直接插入排序.gif

代码实现如下:

/*
 * 直接插入排序
 * 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 获取。

如有错误,还请指正。

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

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



这篇关于【排序算法动画解】直接插入排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程