动图图解C语言插入排序算法，含代码分析

C语言中文社区

发布于 2022-05-31 09:25:15

7260

发布于 2022-05-31 09:25:15

文章被收录于专栏：C语言中文社区C语言中文社区

插入排序算法的原理

将待排序序列分成两个序列，前面的序列保持有序，依次选取后面的序列的元素，在前面的序列中进行插入。

使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

代码实现

#include <stdio.h>

#define N 5  //数组中元素的个数

void print_arr(int *); //将数组打印输出
void insert_sort(int *); //选择排序

int main() {
    int arr[N] = {23, 12, 33, 20, 45}; //定义数组并初始化
    printf("排序前的数据为：\n");
    print_arr(arr);
    printf("开始排序：\n");
    insert_sort(arr);
    printf("排序后的数据为：\n");
    print_arr(arr);
}

void print_arr(int arr[]) {
    //将数组循环遍历输出
    for (int i = 0; i < N; i++) {
        printf("%d\t", arr[i]);
    }
    printf("\n");
}

void insert_sort(int arr[]) {
    int i;  //扫描次数
    int j;  //以j来定位比较的元素
    int temp; //中间变量，暂存数据
    for (i = 1; i < N; i++) {  //循环N-1次(除了第一个元素之外的所有元素)
        temp = arr[i];
        j = i - 1;
        while (j >= 0 && temp < arr[j]) { //对当前元素前面有序表进行待插入位置查找
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
        printf("第%d次扫描：", i);
        print_arr(arr);
    }
}

运行结果

排序前的数据为：
23      12      33      20      45
开始排序：
第1次扫描：12   23      33      20      45
第2次扫描：12   23      33      20      45
第3次扫描：12   20      23      33      45
第4次扫描：12   20      23      33      45
排序后的数据为：
12      20      23      33      45