插入排序算法详解
插入排序是一种相对较简单的排序算法,它可以实现在不断输入元素的同时对数据进行排序,即所有元素输入完毕后,就可以立刻得到由输入数据组成的有序序列。
图 1 待排序元素 X
通过执行一次插入排序操作,元素 X 会被插入到已排序序列中的适当位置,如图 2 所示。
图 2 插入到适当位置的元素 X
由此,通过不断重复执行图 1 到图 2 的过程,直到最后一个元素,即可实现对整个序列的排序。
举个例子,接下来使用插入排序算法对 (5,1,4,2,8) 这个序列进行排序,其初始状态如图 3 所示。
图 3 未排序之前的序列状态
注意,既然是要做插入排序,那么序列中第一个元素本身是不需要移动的,换句话说,在做插入排序操作之前,序列中第一个元素就默认是已经排序好的,它位于已排序序列中。
第一次扫描待排序序列,得到元素 1,做插入排序操作,其结果如图 4 所示。
图 4 插入元素 1 之后的状态
继续扫描待排序序列,得到元素 4,做插入排序操作,其结果如图 5 所示。
图 5 插入元素 4 之后的状态
继续扫描待排序序列,得到元素 2,做插入排序操作,其结果如图 6 所示。
图 6 插入元素 2 之后的状态
继续扫描待排序序列,得到元素 8,做插入排序操作,其结果如图 7 所示。
图 7 插入元素 8 之后的状态
由此,插入排序算法结束,得到排序好的序列 (1,2,4,5,8)。
实现代码如下(C 语言):
插入排序的基本原理是从前往后扫描待排序序列,并依次将扫描到的元素插入到已排序序列中的适当位置。如图 1 所示,假设现在扫描到了 X,X 前面的为已排序序列,后面的为未排序序列。插入排序属于稳定的排序算法,即当待排序序列中有相同的元素时,它们的相对位置在排序前后不会发生改变。
图 1 待排序元素 X
通过执行一次插入排序操作,元素 X 会被插入到已排序序列中的适当位置,如图 2 所示。
图 2 插入到适当位置的元素 X
由此,通过不断重复执行图 1 到图 2 的过程,直到最后一个元素,即可实现对整个序列的排序。
举个例子,接下来使用插入排序算法对 (5,1,4,2,8) 这个序列进行排序,其初始状态如图 3 所示。
图 3 未排序之前的序列状态
注意,既然是要做插入排序,那么序列中第一个元素本身是不需要移动的,换句话说,在做插入排序操作之前,序列中第一个元素就默认是已经排序好的,它位于已排序序列中。
第一次扫描待排序序列,得到元素 1,做插入排序操作,其结果如图 4 所示。
图 4 插入元素 1 之后的状态
继续扫描待排序序列,得到元素 4,做插入排序操作,其结果如图 5 所示。
图 5 插入元素 4 之后的状态
继续扫描待排序序列,得到元素 2,做插入排序操作,其结果如图 6 所示。
图 6 插入元素 2 之后的状态
继续扫描待排序序列,得到元素 8,做插入排序操作,其结果如图 7 所示。
图 7 插入元素 8 之后的状态
由此,插入排序算法结束,得到排序好的序列 (1,2,4,5,8)。
实现代码如下(C 语言):
#include <stdio.h> #define N 5 int a[N] = { 5,1,4,2,8 }; //插入排序函数 void InsertSort(int a[]) { for (int i = 1; i < N; i++) { //若第 i 个元素大于 i-1 元素则直接插入;反之,需要找到适当的插入位置后在插入 if (a[i] < a[i - 1]) { int j = i - 1; int x = a[i]; //采用顺序查找方式找到插入的位置,在查找的同时,将数组中的元素进行后移操作,给插入元素腾出空间 while (j > -1 && x < a[j]) { a[j + 1] = a[j]; j--; } a[j + 1] = x; //插入到正确位置 } //输出插入排序后的序列 printf("第 %d 次:", i); for (int i = 0; i < N; i++) { printf("%d ", a[i]); } printf("\n"); } } int main() { InsertSort(a); return 0; }运行结果为:
第 1 次:1 5 4 2 8
第 2 次:1 4 5 2 8
第 3 次:1 2 4 5 8
第 4 次:1 2 4 5 8
O(n2)
,最优时间复杂度为O(n)
(即当待排序序列已经有序的情况下),平均时间复杂度为O(n2)
。所有教程
- C语言入门
- C语言编译器
- C语言项目案例
- 数据结构
- C++
- STL
- C++11
- socket
- GCC
- GDB
- Makefile
- OpenCV
- Qt教程
- Unity 3D
- UE4
- 游戏引擎
- Python
- Python并发编程
- TensorFlow
- Django
- NumPy
- Linux
- Shell
- Java教程
- 设计模式
- Java Swing
- Servlet
- JSP教程
- Struts2
- Maven
- Spring
- Spring MVC
- Spring Boot
- Spring Cloud
- Hibernate
- Mybatis
- MySQL教程
- MySQL函数
- NoSQL
- Redis
- MongoDB
- HBase
- Go语言
- C#
- MATLAB
- JavaScript
- Bootstrap
- HTML
- CSS教程
- PHP
- 汇编语言
- TCP/IP
- vi命令
- Android教程
- 区块链
- Docker
- 大数据
- 云计算