插入排序算法

插入排序算法可以对指定序列完成升序（从小到大）或者降序（从大到小）排序，对应的时间复杂度为O(n2)。

插入排序算法的实现思路是：初始状态下，将待排序序列中的第一个元素看作是有序的子序列。从第二个元素开始，在不破坏子序列有序的前提下，将后续的每个元素插入到子序列中的适当位置。

举个简单的例子，用插入排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 实现升序排序的过程如下：

1) 将第一个元素 14 看作是一个有序的子序列 {14}，将剩余元素逐个插入到此序列的适当位置：

2) 将 33 插入到 {14} 中，由于 33 > 14，所以 33 应该插入到 14 的后面，新的有序序列变为 {14, 33}；

3) 将 27 插入到 {14, 33} 中，由于 27 < 33 同时 27 > 14，所以 27 应该插入到 14 和 33 的中间，新的有序序列变为 {14, 27, 33}；

4) 将 10 插入到 {14, 27, 33} 中，经过依次和 33、27、14 比较，最终断定 10 应该插入到 14 之前，新的有序序列变为 {10, 14, 27, 33}；

5) 将 35 插入到 {10, 14, 27, 33} 中，由于 35 > 33，所以 35 应该插入到 33 之后，新的有序序列变为 {10, 14, 27, 33, 35}；

6) 将 19 插入到 {10, 14, 27, 33, 35} 中，经过依次和 35、33、27、14 比较，最终断定 19 应该插入到 14 和 27 之间，新的有序序列变为 {10, 14, 19, 27, 33, 35}；

7) 将 42 插入到 {10, 14, 19, 27, 33, 35} 中，由于 42 > 35，所以 42 应插入到 35 之后，新的有序序列变为 {10, 14, 19, 27, 33, 35, 42}；

8) 将 44 插入到 {10, 14, 19, 27, 33, 35, 42} 中，由于 44 > 42，所以 44 应插入到 42 之后，新的有序序列变为 {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

结合伪代码，如下是用插入排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 实现升序排序的C语言程序：

1. #include <stdio.h>
2. #define MAX 8   //设定待排序序列中的元素个数
3. //list[MAX]为待排序序列
4. void insertion_sort(int list[MAX]) {
5. int insert_elem;
6. int position;
7. int i;
8. 
   
9. //从第 2 个元素（下标为 1）开始遍历
10. for (i = 1; i < MAX; i++) {
11. // 记录要插入的目标元素
12.        insert_elem = list[i];
13. // 记录目标元素所在的位置，从此位置向前开始遍历
14.        position = i;
15. 
    
16. // 从 position 向前遍历，找到目标元素的插入位置
17. while (position > 0 && list[position - 1] > insert_elem) {
18. //position 处的元素向后移动一个位置
19.            list[position] = list[position - 1];
20.            position--;
21. }
22. //将目标元素插入到指定的位置
23. if (position != i) {
24.            list[position] = insert_elem;
25. }
26. }
27. }
28. 
    
29. int main() {
30. int i;
31. int list[MAX] = { 14, 33, 27, 10, 35, 19, 42, 44 };
32. insertion_sort(list);
33. //输出 list 数组中已排好序的序列
34. for (i = 0; i < MAX; i++) {
35. printf("%d ", list[i]);
36. }
37. }

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

1. public class Demo {
2. public static void insertion_sort(int[] list) {
3. int length = list.length;
4. // 从第 2 个元素（下标为 1）开始遍历
5. for (int i = 1; i < length; i++) {
6. // 记录要插入的目标元素
7. int insert_elem = list[i];
8. // 记录目标元素所在的位置，从此位置向前开始遍历
9. int position = i;
10. // 从 position 向前遍历，找到目标元素的插入位置
11. while (position > 0 && list[position - 1] > insert_elem) {
12. // position 处的元素向后移动一个位置
13.                list[position] = list[position - 1];
14.                position--;
15. }
16. // 将目标元素插入到指定的位置
17. if (position != i) {
18.                list[position] = insert_elem;
19. }
20. }
21. }
22. 
    
23. public static void main(String[] args) {
24. int[] list = { 10, 14, 19, 27, 33, 35, 42, 44 };
25. insertion_sort(list);
26. // 输出已排好序的序列
27. for (int i = 0; i < list.length; i++) {
28.            System.out.print(list[i] + " ");
29. }
30. }
31. }

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

1. #待排序序列
2. list = [10, 14, 19, 27, 33, 35, 42, 44]
3. def insertion_sort():
4.    length = len(list)
5. # 从第 2 个元素（下标为 1）开始遍历
6. for i in range(1,length):
7. # 记录要插入的目标元素
8.        insert_elem = list[i];
9. # 记录目标元素所在的位置，从此位置向前开始遍历
10.        position = i
11. # 从 position 向前遍历，找到目标元素的插入位置
12. while position > i and list[position - 1] > insert_elem:
13. # position 处的元素向后移动一个位置
14.            list[position] = list[position - 1]
15.            position = position - 1
16. # 将目标元素插入到指定的位置
17. if position != i:
18.            list[position] = insert_elem
19. 
    
20. insertion_sort()
21. # 输出已排好序的序列
22. for i in list:
23. print(i,end=" ")

以上程序的输出结果均为：

10 14 19 27 33 35 42 44