直接插入排序

151 阅读 0 评论 100 点赞

我是靠谱客的博主坦率红酒，这篇文章主要介绍直接插入排序，现在分享给大家，希望可以做个参考。

算法思想：
对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余的记录为无序序列；接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。

代码很简单，详见代码注释：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

void insertSort(int arr[], int len)
{
    int i,j,temp;
    for (i = 1; i < len; i++) // 初始时，下标0对应的第一个记录看成是初始有序区。所以，从下标1开始。
    {
        temp = arr[i];  // 待插入的记录

        for (j = i - 1; j >= 0; j--) // 在已有的有序区中，采用从后向前的顺序查找方式来查找，j>=0 是防止数组越界
        {
            if (temp < arr[j]) // 若“待插入数据temp”比当前的数据小，则把当前的数据后移一个位置。若发生了后移，则会覆盖掉原数组中“此次待插入的数据arr[i]“的值，但是没影响，因为arr[i]已经保存在temp中了。
            {
                arr[j + 1] = arr[j];
            }
            else
                break; // 若“待插入的数据”比当前的数据大，说明找到了正确的插入位置，退出循环。
        }

        arr[j + 1] = temp; // 退出循环，说明找到了插入位置，因为arr[j]刚刚比较完毕，所以j+1为正确的插入位置。
    }
}


int main(int argc, const char * argv[]) {

    int arr[] = {2,5,8,1,3,6,9,0,4,7};
    int len = sizeof(arr)/sizeof(int);

    insertSort(arr, len);

    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);

    printf("n");

    return 0;
}