直接插入排序算法实现思想个人理解

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

3.整个代码如下：

    #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];
        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;
    }

直接插入排序算法实现思想个人理解

相关推荐