前言

本文记录数据结构考试中常用几种算法

插入排序

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 [。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

上述看看就行

插入排序核心代码:

void Insert_Sort(int A[], int len) {
    int i, j;
    //第0个位置存储哨兵,第1个元素天然有序,
    for (i = 2; i <=len; ++i) {//从第二个元素开始 往前插入,i控制有序序列
        if (A[i - 1] > A[i]) {
            A[0] = A[i];//将较小的元素放到暂存位置充当哨兵值
            //j=i-1,表示从插入元素前一个元素开始遍历
            //j控制有序序列中的每一个元素和要插入的元素进行比较
            for (j = i - 1; A[j] > A[0]; --j) {
                A[j + 1] = A[j];

            }
            A[j + 1] = A[0];//把暂存位置插入对应位置

        }

    }

}

我们的数据中A[0]是作为哨兵位置,所以在打印过程中,是不参与比较的

大概解释一下代码,我们的i从2开始,是因为第0个元素当做了哨兵暂存较小值,第一个元素从排序角度来看是天然有序的,所以如果要进行比较我们是从第二个元素开始的

而当i前面的元素比如int A[0]如果大于A[1]的时候,我们把A[1]的值暂存于A[0]处后续插入

而j从i-1开始是为了和前方有序序列中的每一个元素进行比较,后确定插入的位置

而A[j] > A[0]是临界条件,当A[j] > A[0],j不断自减,直到出现一个A[j] <A[0]的时候就表示这时我们要从这里插入哨兵元素

A[j+1]=A[j]表示当A[j] > A[0]时,我们需要不断的把较大的元素往后覆盖

当关于j的for循环结束的时候,我们需要把哨兵元素插入进我们刚才在循环中找到的A[j] <A[0]处

我们可以通过一些数据来手动实现这个过程

测试数据示例:

原始数据: 49(哨兵位置) 38 65 97 76 13 27 49

输入原始数据中中第一个49被当做了初始哨兵

第一趟:哨兵位置为76 38 65 76 97 13 27 49

第二趟:哨兵位置为13 13 38 65 76 97 27 49

第三趟:哨兵位置为27 13 27 38 65 76 97 49

第四趟:哨兵位置为49 13 27 38 49 65 76 97

排序最终结果为:

13 27 38 49 65 76 97

总体代码为

//
// Created by 28015 on 2022/8/2.
//

#include <cstdio>
void arr_print(int arr[], int len) {
    for (int i = 0; i < len; ++i) {
        printf("%3d ", arr[i]);
    }
    printf("\n");
}

void Insert_Sort(int A[], int len) {
    int i, j;
    //第0个位置存储哨兵,第1个元素天然有序,
    for (i = 2; i <= len; ++i) {//从第二个元素开始 往前插入,i控制有序序列
        if (A[i - 1] > A[i]) {
            A[0] = A[i];//将较小的元素放到暂存位置充当哨兵值
            //j=i-1,表示从插入元素前一个元素开始遍历
            //j控制有序序列中的每一个元素和要插入的元素进行比较
            for (j = i - 1; A[j] > A[0]; --j) {
                A[j + 1] = A[j];
            }
            A[j + 1] = A[0];//把暂存位置插入对应位置
        }
    }
}


int main() {
    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int len = sizeof(arr) / sizeof(arr[0]);
    Insert_Sort(arr, len);
    arr_print(arr,len);

}