直接插入排序

本文章的代码使用jetbrains公司旗下的的Clion编写，操作系统位macOS Ventura(13.2.1). 代码没有在dev-c++测试过（dev-c++可能会有相关的空格问题）

#define Max 100
#define before  printf("排序前")
#define after   printf("排序后")
#define newline printf("\n")
#define print   printf("%6d", R[i].key)
#define printA  printf("%6d",A[i])
#define Array int A[]={5,7,2,5,9,6,42,1,67,2,3};


//直接插入算法是一种最简单的插入算法，其过程是依次讲每个元素插入到一个有序的序列中
#include "stdio.h"

typedef struct {
    int key ;
    int data;  //对于排序来说，这个data并没有起到任何作用
}SqType;


//直接插入排序每趟产生的有序区并不一定是全局有序区，也就是说有序区的元素并不一定放在最终的位置，当一个元素在整个排序结束之前就已经=放在其最终的位置，称为归位
//数据结构上的算法，对相关数据测试的时候需要将相关的数据送入结构体的key，对于key和相关的data 也没有使用别名
void insertSort(SqType R[] ,int n){
    int i,j;
    SqType temp;
    for (i = 1; i < n; i++) {
        if (R[i - 1].key > R[i].key) {
            temp = R[i];
            j = i - 1;
            do {
                R[j + 1] = R[j];
                j--;
            } while (j >= 0 && R[j].key > temp.key);
            R[j + 1] = temp;
        }
    }
}

// 直接插入排序优化后的函数
void insertSort_1(int A[], int n) {
    for (int i = 1; i < n; i++) {
        if (A[i - 1] > A[i]) { // 如果当前元素比前一个元素小，则需要将当前元素插入到有序区中
            int temp = A[i]; // 将当前元素存储在临时变量temp中
            int j = i - 1; // j用于在有序区中寻找插入位置
            // 在有序区中寻找插入位置，同时将大于temp的元素向右移动一位
            while (j >= 0 && A[j] > temp) {
                A[j + 1] = A[j]; // 将元素向右移动一位
                j--;
            }
            A[j + 1] = temp; // 将当前元素放置在正确的位置上
        }
    }
}



int  main(){
    SqType R[Max];
    Array;
    for (int i = 0; i < 10; i++)
        R[i].key = A[i];
before;
    for (int i = 0; i < 10; i++)
        print;
newline;
    insertSort(R,10);
after;
    for (int i = 0; i < 10; i++)
        print;
newline;
    insertSort_1(A,10);
after;
    for (int i = 0; i < 10; i++)
        printA;
}

相关的测试结果如下