直接插入排序法

任务描述
本关任务：要求编写程序实现直接插入排序的功能。

相关知识
直接插入排序，是指将无序序列中的各元素依次插入到已经有序的数组中。

假设数组中前 i-1 元素已经有序，现在要将线性表中第 i 个元素插入到前面的有序子表中，插入过程如下：

以长度为 n=8 的序列 （13，6，1，31，9，27，5，11） 的插入排序过程做示范：
第 1 趟：将数组第 2 个元素 6 向前插入后，则数组中元素为 （6，13，1，31，9，27，5，11）；
第 2 趟：将数组第 3 个元素 1 向前插入后，则数组中元素为 （1，6，13，31，9，27，5，11）；
第 3 趟：将数组第 4 个元素 31 向前插入后，则数组中元素为 （1，6，13，31，9，27，5，11）；
……
第 7 趟：将数组第 8 个元素 11 向前插入后，则数组中元素为 （1，5，6，9,11，13，27，31）；
总之，共执行 7 趟操作，可将有 n=8 个元素的数组排成有序序列。

#include <stdio.h>
#include <stdlib.h>
#define N 100

int main() {
    int n, i, j, temp;
    int a[N];

    // 读取非负整数N
    scanf("%d", &n);
    
    // 读取N个整数
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    // 直接插入排序
    for (i = 1; i < n; i++) {
        temp = a[i]; // 当前要插入的元素
        for (j = i - 1; j >= 0 && a[j] > temp; j--) {
            a[j + 1] = a[j]; // 后移
        }
        a[j + 1] = temp; // 插入
        
        // 输出每次插入排序后的结果
        for (int k = 0; k < n; k++) {
            printf("%d ", a[k]);
        }
        printf("\n");
    }
    
    return 0;
}

原文地址：https://blog.csdn.net/lightfuturezyx99/article/details/143679885

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！