算法基础三：插入排序

定义

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 {\displaystyle O(1)} {\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后

挪位，为最新元素提供插入空间。

特性

1.时间复杂度

最好情况就是全部有序，此时只需遍历一次，最好的时间复杂度为O ( n ) O(n)O(n)
最坏情况全部反序，内层每次遍历已排序部分，最坏时间复杂度为O ( n 2 ) O(n^2)O(n2)

综上，因此直接插入排序的平均时间复杂度为O ( n 2 ) O(n^2)O(n2)

2.空间复杂度

辅助空间是常量
平均的空间复杂度为：O ( 1 ) O(1)O(1)

3.算法稳定性

相同元素的前后顺序是否改变

插入到比它大的数前面，所以直接插入排序是稳定的

举例说明原理

原理文字太枯燥了，以下用数组3,4,6,7,9,1,2,5为例
从小到大排序

1、首先选择第一个数，由于第一个数必然有序，丨前面为有序组、后面为无序。

3 | 6 7 9 1 2 5

2、取出无序部分的首个，在有序部分从后向前比较，插入到合适的位置

3 6 | 7 9 1 2 5

3、重复第2步直到无序部分全部插入有序，7和9也是一次比较就可以插入

3 6 7 | 9 1 2 5

3 6 7 9 | 1 2 5

4、1就需要多次比较，注意是多次比较，直接插入，不是比较一次插入一次（与冒泡不同）

3 6 7 9 口 | 2 5
temp = 1

可以看到先把1放到temp中，与前面比较，最后放到合适位置

1 3 6 7 9 | 2 5

5、后面就重复上面操作

1 2 3 5 6 7 9

以下为C语言代码并附上代码解析带图

一：C语言代码

#include <stdio.h>// 函数声明
void insertion_sort(int arr[], int len);int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = sizeof(arr) / sizeof(arr[0]);  // 计算数组长度insertion_sort(arr, len);  // 调用插入排序函数// 打印排序后的数组for (int i = 0; i < len; i++) {printf("%d ", arr[i]);}return 0;
}
void insertion_sort(int arr[], int len) {for (int i = 1; i < len; i++){int temp = arr[i];int j = i;while (j > 0 && arr[j - 1] > temp) {arr[j] = arr[j - 1];j--;}arr[j] = temp;}
}

二：代码解析

1、我们逐句分析，先看第一句，很简单从数组地址为1开始遍历

3 | 6 7 9 1 2 5

for (int i = 1; i < len; i++)

2、将数放进temp中，地址存进j中

 int temp = arr[i];int j = i;

3 口 | 7 9 1 2 5
temp = 6
6所在地址1存进j中

3、前面还有数并且取出的数小于有序组最后一个

while (j > 0 && arr[j - 1] > temp)

3 7 9 口| 2 5
temp = 11前面有数并且9>1

4、前面比他大的数往后移；接着地址减小再进while

 arr[j] = arr[j - 1];j--;

3 7 口 9| 1 2 5
temp = 1

5、最终放到合适地方

 arr[j] = temp;

口 3 7 9 | 2 5
temp = 1放下以后：1 3 7 9 | 2 5

如下是用插入排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 实现升序排序的 Python 程序：

#待排序序列
list = [10, 14, 19, 27, 33, 35, 42, 44]
def insertion_sort():length = len(list)# 从第 2 个元素（下标为 1）开始遍历for i in range(1,length):# 记录要插入的目标元素insert_elem = list[i];position = i# 从 position 向前遍历，找到目标元素的插入位置while position > 0 and list[position -1] > insert_elem:#position 处的元素向后移动一个位置list[position]  = list[position -1];position = position-1# 将目标元素插入到指定的位置if position != i:list[position] = insert_elem
insertion_sort()# 输出已排好序的序列
for i in list:print(i,end=" ")