直接插入排序（Insertion Sort）|笔记|Code001

vlambda
2021-08-25

直接插入排序（Insertion Sort）|笔记|Code001

算法日记

一、文章结构

1、算法思想及排序过程

2、算法

3、示例代码

4、碎碎念

软件默认：VS2017 | Python3.8.5 | PyCharm2019.1.2 | IDEA2019.3.3 | Anconda3_2020.11

图源菜鸟教程：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

后台回复 Code 四个字母即可直达此系列。

点击标题下方 #Code 可连续阅读。

源码：后台回复 20210809001（今日无暗号）

暗号组成：当天发文日期+标题Code数字编号

注：默认升序排序

二、算法思想及排序过程

直接插入排序是一种最简单的插入排序算法。

基本算法思想：假设待排序元素有n个，初始时，有序集合中只有1个元素，无序集合中是剩下的n-1个元素。

主要用途：直接插入排序算法实现简单，适用于待排序元素较少且基本有序的情况。在元素基本有序时，需要比较的次数和移动的次数很少，因此在这种情况下使用直接插入排序最佳。

稳定性与复杂度：直接插入排序属于稳定的排序方法，直接插入排序算法的时间复杂度为直接插入排序（Insertion Sort）|笔记|Code001 ，空间复杂度为。

示例：4个待排序元素——35、12、5、21

初始时：

35	12	5	21
有序集	无序集

第1趟排序过程：将无序集中第1个元素12，与有序集中的元素35相比较。因为35＞12，所以35右移1个位置，12插入到有序集的第一个位置。

第1趟排序结果：

12	35	5	21
有序集		无序集

第2趟排序过程：将无序集中第2个元素5，与有续集中的元素从右到左比较。即，先将5与35比较，因为35＞5，所以先将35移动一个位置，然后将5与12比较，因为5＜12，所以将12右移一个位置，将5放在第一个位置。

第2趟排序结果：

5	12	35	21
有序集			无序集

第3趟排序过程：将无序集中元素21从右到左依次与有序集中元素比较。因为21＜35，则将35右移一个位置，21＞12，故将其放在12与35之间。

第三趟排序结果：

5	12	21	35
有序集

当无序集变为空集时，排序完毕，整个序列变得有序。

三、算法

//Straight Insertion Sortvoid InserationSort(int a[], int n) { int i, j, tmp;
 for (i = 1; i < n; i++) { //比较n-1趟 int tmp = a[i]; //无序组第一个元素
 //右移条件：tmp＜有序组元素，j是有序组最后一个元素开始从左到右 for(j = i - 1; j >= 0 && tmp < a[j]; j--){ //tmp依次从右到左与有序组比较 a[j + 1] = a[j]; //有序组右移 }    a[j + 1] = tmp;      //不右移    printf("第%d趟排序结果：", i); }}

四、示例代码

//直接插入排序（Straight Insertion Sort）//直接复制此处即可运行
#include<stdio.h>void PrintArray(int a[], int n); //显示长度为n的数组void InserationSort(int a[], int n);//Straight Insertion Sort
int main(int argc, char *argv[]) { int a[] = { 35, 12, 5, 21 }; int n = sizeof(a) / sizeof(a[0]);
 printf("排序前：\n"); PrintArray(a, n); printf("\n排序后：\n"); InserationSort(a, n);
 return 0;}
//显示长度为n的数组void PrintArray(int a[], int n){ int i; for (i = 0; i < n; i++) printf("%4d", a[i]); printf("\n");}
//Straight Insertion Sortvoid InserationSort(int a[], int n) { int i, j, tmp;
 for (i = 1; i < n; i++) { //比较n-1趟 int tmp = a[i]; //无序组第一个元素
 //右移条件：tmp＜有序组元素，j是有序组最后一个元素开始从左到右 for(j = i - 1; j >= 0 && tmp < a[j]; j--){ //tmp依次从右到左与有序组比较 a[j + 1] = a[j]; //有序组右移 } a[j + 1] = tmp; //不右移
 printf("第%d趟排序结果：", i); PrintArray(a, n); }}

运行截图：

直接插入排序（Insertion Sort）|笔记|Code001

五、碎碎念

心平气和做好每一件小事。

今夜无语。

直接插入排序（Insertion Sort）|笔记|Code001

参考文献：

[1].《C/C++数据结构与算法速学速用大辞典》

[2].https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

不唐的成长笔记

江湖不会等你把刀配好

70篇原创内容

Official Account

vlambda博客
学习文章列表