直接插入排序算法，C语言代码实例详解

菜小编

2022-7-17

数据结构与算法

1. 复杂度与稳定性

最坏情况：O(N^2)

最好情况：O(N^2)

平均情况：O(N^2)

稳定性：稳定排序

2. 过程介绍

直接插入排序是把新的数据插入以及排序好的数列中，排序的基本方法是：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。

可以选择不同的方法在已经排好序数据表中寻找插入位置。根据查找方法不同，有多种插入排序方法，下面要介绍的是直接插入排序。

1. 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

2. 第一趟比较前两个数，然后把第二个数按大小插入到有序表中；

3. 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；

4. 依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

3.图示过程

以数组数据{ 70,50,30,20,10,70,40,60}为例：

第一趟	50	70	30	20	10	70	40	60
第二趟	30	50	70	20	10	70	40	60
第三趟	20	30	50	70	10	70	40	60
第四趟	10	20	30	50	70	70	40	60
第五趟	10	20	30	50	70	70	40	60
第六趟	10	20	30	40	50	70	70	60
第七趟	10	20	30	40	50	60	70	70
第八趟	10	20	30	40	50	60	70	70

将红色的数据依次插入组成一个逐渐有序的数组

4. 相关的代码

#include<iostream>
using namespace std;
void insert_sort(int a[],int n) {
    int i,j;
    for(i=1; i<n; i++) { //循环从第2个元素开始
        if(a[i]<a[i-1]) {
            int temp=a[i];
            for(j=i-1; j>=0 && a[j]>temp; j--) {
                a[j+1]=a[j];
            }
            a[j+1]=temp;//此处就是a[j+1]=temp;
        }
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=7;
    insert_sort(a,n);
    for(int i=0; i<=n; i++) {
        cout<<a[i]<<' ';
    }
    return 0;
}

THE END