薇老大
插入排序是一种非常简单的排序算法，它可以对序列完成升序（由小到大）或降序（由大到小）排序。
插入排序算法的核心思想是：始终维护一个有序的子序列，并不断将其它待排序的元素插入到这个有序序列中，直至该序列包含所有待排序的元素。
插入排序算法并不适用于对大型数据集进行排序，其平均时间复杂度为O(n2)。
插入排序算法的基本原理
我们以如下待排序的序列为例，给您描述使用插入排序算法进行升序排序的整个过程。
1) 首先，我们默认第 1 个元素 14 为一个有序的子序列，依次将剩余元素插入到该序列中。
2) 比较 33 和 14 的大小，14 < 33，符合升序排序的规则，因此有序子序列变为 {14,33}。
3) 比较 33 和 27 的大小，33 > 27，不符合升序排序的规则，27 应插入到 14 和 33 中间，有序子序列变为 {14,27,33}。
4) 比较 33 和 10 的大小，33 > 10，不符合升序排序的规则，10 应插入到 14 前面，有序子序列变为 {10,14,27,33}。
5) 比较 33 和 35 的大小，33 < 35，符合升序排序的规则，有序自序列变为 {10,14,27,33,35}。
6) 比较 35 和 19 的大小，35 > 19，不符合升序排序的规则，19 应插入到 14 和 27 之间，有序子序列变为 {10,14,19,27,33,35}。
7) 比较 35 和 42 的大小，35 < 42，符合升序排序的规则，有序子序列变为 {10,14,19,27,33,35,42}。
8) 比较 42 和 44 的大小，42 < 44，符合升序排序的规则，有序子序列变为 {10,14,19,27,33,35,42,44}。
由此，我们就得到了 {10,14,19,27,33,35,42,44} 这个升序序列。
插入排序算法的具体实现
如下为实现插入排序算法的伪代码：
// list 为待排序序列
insertion_sort(list):
// 从第 2 个元素开始遍历序列
for i <- 2 to length(list):
//记录要插入的目标元素
insert_elem = list[i]
//记录目标元素所在的位置
position = i
//从 position 所在位置向前遍历，直至找到一个比目标元素小的元素，目标元素插入到该元素之后的位置
while position > 0 and list[position-1] > insert_elem: // 此为升序排序，实现降序排序改为 list[position-1] < insert_elem
//移动前一个元素的位置，将其向后移动一个位置
list[position] = list[position-1]
position = position - 1
if(position != i):
list[position] = insert_elem
return list
如下是用插入排序算法对 {10,14,19,27,33,35,42,44} 进行升序排序的 C 语言程序：
#include <stdio.h>
#define MAX 8 //设定待排序序列中的元素个数
//list[MAX]为待排序序列
void insertion_sort(int list[MAX]) {
int insert_elem;
int position;
int i;
//从第 2 个元素（下标为 1）开始遍历
for (i = 1; i < MAX; i++) {
// 记录要插入的目标元素
insert_elem = list[i];
// 记录目标元素所在的位置，从此位置向前开始遍历
position = i;
// 从 position 向前遍历，找到目标元素的插入位置
while (position > 0 && list[position - 1] > insert_elem) {
//position 处的元素向后移动一个位置
list[position] = list[position - 1];
position--;
}
//将目标元素插入到指定的位置
if (position != i) {
list[position] = insert_elem;
}
}
}
int main() {
int list[MAX] = { 10,14,19,27,33,35,42,44 };
insertion_sort(list);
//输出 list 数组中已排好序的序列
for (int i = 0; i < MAX; i++) {
printf("%d ", list[i]);
}
}
如下是用插入排序算法对 {10,14,19,27,33,35,42,44} 进行升序排序的 Java 程序：
public class Demo {
public static void insertion_sort(int[] list) {
int length = list.length;
// 从第 2 个元素（下标为 1）开始遍历
for (int i = 1; i < length; i++) {
// 记录要插入的目标元素
int insert_elem = list[i];
// 记录目标元素所在的位置，从此位置向前开始遍历
int position = i;
// 从 position 向前遍历，找到目标元素的插入位置
while (position > 0 && list[position - 1] > insert_elem) {
// position 处的元素向后移动一个位置
list[position] = list[position - 1];
position--;
}
// 将目标元素插入到指定的位置
if (position != i) {
list[position] = insert_elem;
}
}
}
public static void main(String[] args) {
int[] list = { 10, 14, 19, 27, 33, 35, 42, 44 };
insertion_sort(list);
// 输出已排好序的序列
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
}
如下是用插入排序算法对 {10,14,19,27,33,35,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 > i 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=" ")
以上程序的输出结果均为：
10 14 19 27 33 35 42 44
