c++插入排序详解

1. 插入排序算法介绍

插入排序法是一种简单直观的排序方法。它的基本思路是通过每次将一个待排序的元素按照其大小插入到已经排好序的一组元素中，直到全部元素插入完毕，即排序完毕。

在实际应用中，对于较小的数据集，插入排序通常比快速排序和归并排序等复杂度为O(nlogn)的算法执行效率更高。

2. 插入排序算法的实现

下面给出一个C++实现的插入排序算法，其中参数arr为待排序的数组，len为数组中元素个数：

void insertSort(int arr[], int len) {
    for (int i = 1; i < len; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j>=0 && arr[j]>key) {
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = key;
    }
}

3. 插入排序算法的示例说明

以下分别给出插入排序算法的两个示例说明：

示例1

给定一个数组arr={5, 2, 6, 7, 1}，按照从小到大的顺序进行插入排序。

初始状态

步骤	0	1	2	3	4
arr	5	2	6	7	1

第一次排序

将2插入到已经排序好的5之前：

步骤	0	1	2	3	4
arr	2	5	6	7	1

第二次排序

将6插入到已经排序好的2，5之后：

步骤	0	1	2	3	4
arr	2	5	6	7	1

第三次排序

将7插入到已经排序好的2，5，6之后：

步骤	0	1	2	3	4
arr	2	5	6	7	1

第四次排序

将1插入到已经排序好的2之前：

步骤	0	1	2	3	4
arr	1	2	5	6	7

因此，最终排序结果为：1 2 5 6 7。

示例2

给定一个数组arr={3, 1, 4, 6, 3, 9, 0, 8, 7}，按照从小到大的顺序进行插入排序。

初始状态

步骤	0	1	2	3	4	5	6	7	8
arr	3	1	4	6	3	9	0	8	7

第一次排序

将1插入到已经排序好的3之前：

步骤	0	1	2	3	4	5	6	7	8
arr	1	3	4	6	3	9	0	8	7

第二次排序

将4插入到已经排序好的1，3之后：

步骤	0	1	2	3	4	5	6	7	8
arr	1	3	4	6	3	9	0	8	7

第三次排序

将6插入到已经排序好的1，3，4之后：

步骤	0	1	2	3	4	5	6	7	8
arr	1	3	4	6	3	9	0	8	7

第四次排序

将3插入到已经排序好的1之前：

步骤	0	1	2	3	4	5	6	7	8
arr	1	3	4	6	3	9	0	8	7

第五次排序

将9插入到已经排序好的1，3，4，6之后：

步骤	0	1	2	3	4	5	6	7	8
arr	1	3	4	6	3	9	0	8	7

第六次排序

将0插入到已经排序好的1之前：

步骤	0	1	2	3	4	5	6	7	8
arr	0	1	3	4	6	3	9	8	7

第七次排序

将8插入到已经排序好的0，1，3，4，6之后：

步骤	0	1	2	3	4	5	6	7	8
arr	0	1	3	4	6	3	9	8	7

第八次排序

将7插入到已经排序好的0，1，3，4，6，8之后：

步骤	0	1	2	3	4	5	6	7	8
arr	0	1	3	4	6	3	9	8	7

因此，最终排序结果为：0 1 3 4 6 7 8 9。