技术交流QQ群:1027579432，欢迎你的加入！

一.原理

  • 由于是直接插入排序，下面假设原始数组中已经有一个元素是5，待插入的元素是3,所以下面的程序中待插入元素的下标i从2开始。数组下标0的位置作为哨兵，暂存待插入的元素。直接插入算法的主要步骤分3步：首先待插入元素的下标i从2开始移动，循环到数组最大长度对应的索引处L->len；然后，将待插入的元素与前一个元素即下标是i-1的元素进行比较。如果前一个元素比待插入的元素大，此时执行直接插入算法。否则不执行，i继续向后移动一个位置，重新插入一个新的元素。接着，将待插入元素暂存在哨兵L->r[0]处(如下图的①)。再接着，将数组的元素向右移动一个位置(即增量为1，给待插入的元素留个位置，准备插入元素啦，如下图的②)。最后，将暂存在哨兵L->r[0]处的带插入元素放到由于上一步向右移动获得的空白位置处，完成整个插入操作(如下图的③)，整个过程中的增量increment始终等于1。

二.插入过程

直接插入排序.jpg

三.完整代码如下：

```
    #include "iostream"

    using namespace std;

    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 10
    #define N 9

    typedef int Status;
    typedef struct
    {
        int r[MAXSIZE+1];
        int len;
    } Sqlist;

    void show(Sqlist L)
    {
        for (int i = 1; i <= L.len; i++)
            cout << L.r[i] << " ";
        cout << endl;
    }

    // 直接插入排序
    void InsertSort(Sqlist *L)
    {
        int i, j;
        for (i = 2; i <= L->len; i++)
        { // 插入的元素从下标为2开始
            if (L->r[i] < L->r[i - 1])
            {                      // 插入的元素比之前的元素值小，就进行交换操作
                L->r[0] = L->r[i]; // 下标为0的位置存放的是哨兵
                for (j = i - 1; L->r[j] > L->r[0]; j--)
                    L->r[j + 1] = L->r[j]; // 进行移动操作
                L->r[j + 1] = L->r[0];  // 插入新的元素到正确的位置
            }
        }
    }



    int main(){
        Sqlist L0;
        int d[N] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
        for(int i = 0; i < N; i++)
            L0.r[i+1] = d[i];
        L0.len = N;
        cout << "直接插入排序前: ";
        show(L0);
        cout << "直接插入排序后: ";
        InsertSort(&L0);
        show(L0);
        return 0;
    }
```
  • STL实现 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


void InsertSort(vector<int>& v){
    int n = v.size();
    for(int i=1; i < n; ++i){  // 假设第一个元素v[0]以已排好序，从第二个元素开始插入
        int temp = v[i];
        for(int j = i-1; j>=0; --j){
            if(temp < v[j]){
                v[j+1] = v[j];
                v[j] = temp;
            }
            else{
                break;
            }
        }
    }
}

// 打印元素
void PrintV(vector<int>& v){
    for(auto &e: v){
        cout << e << ' ';
    }
    cout << endl;
}

int main(){
    vector<int> v{7, 30, 16, 4, 1, 2, 9};
    cout << "直接插入排序前: ";
    PrintV(v);
    InsertSort(v);
    cout << "直接插入排序后: ";
    PrintV(v);
    return 0;
}

四、直接插入排序时间复杂度总结：

  • 平均时间复杂度：O(n**2)
  • 最好情况：O(n)
  • 最坏情况：O(n**2)
  • 空间复杂度：O(1)
  • 稳定性：稳定