直接插入排序C语言实现

#include <stdio.h>
#include <iostream>
void InsertSort(int a[], int n);  // 不带哨兵的插入排序
void InsertSortWithSentry(int a[], int n);  // 带哨兵的插入排序
void print(int a[], int n, int hasSentry);  //遍历数组

int main() {
    int a[5] = {10, 2, 13, 5, 6};
    // 不带哨兵的插入排序
    // int length = sizeof(a)/sizeof(int);
    // InsertSortWithSentry(a, sizeof(a)/sizeof(int));
    // 带哨兵的插入排序
    int b[6] = {0, 10, 2, 13, 5, 6};
    InsertSortWithSentry(b, sizeof(b)/sizeof(int));
    return 0;
}

// 没有哨兵 sentry 哨兵
void InsertSort(int a[], int n) {
    // a[] 待排序数组  n 数组长度
    int i, j, temp;
    // n - 1 趟插入排序 第一个元素默认是排序好序列
    for (i = 1; i < n; i++) {
        // 用Temp暂存待排序元素，防止前面元素进行后移时覆盖变量
        temp = a[i];
        // 待排序元素前面的序列的最大值如果大于temp 需要进行插入排序
        if (a[i-1] > temp ) {
          for (j = i -1; j >= 0 && a[j] > temp; j--) {
              // 比temp大的元素后移，给待排序元素提供插入空间
              a[j+1] = a[j];
          }  
          a[j+1] = temp; 
        }  
        // 否则 就保持原位置即可 
        printf("第%d次插入排序所得结果：\n", i);
        // 遍历序列
        print(a, n, 0);
        printf("\n");
    }
}

// 有哨兵 即数组第一个空间不存放具体元素 用来暂存待排序元素 n应该是数组实际长度 + 1
void InsertSortWithSentry(int a[], int n) {
    int i ,j;
    // 因为a[0]不存放实际元素，所以插入排序第一趟是从a[2]开始的
    // n - 1趟冒泡排序  
    for (int i = 2; i <= n - 1; i++) {
        // a[0]用于充当“哨兵”，用于暂存待排序元素
        a[0] = a[i];
        if (a[i-1] > a[i]) {
            // 哨兵的好处就是不用考虑数组越界，在没有哨兵的第一种方法中，我们可以发现判断多了一条j >= 0 
            // 但是这里，因为a[0]（即哨兵）存放的元素和待排序元素相等，所以和a[0]比较时，必定退出for循环
            // 不会出现数组越界的情况
            for (j = i - 1; a[j] > a[0]; j--) {
                // 比待排序元素大的元素后移，给待排序元素腾出插入空间
                a[j + 1] = a[j];
            } 
            // 将待排序元素插入到腾出的位置， 完成此趟插入排序
            a[j + 1] = a[0];
        }  // if
        // 如果前面已排序好的序列的最大值比待排序序列小，则不需要移动任何元素

        // 输出
        printf("第%d次插入排序所得结果：\n", i - 1);
        // 遍历序列
        print(a, n, 1);
        printf("\n");

    } // for
}

// 输出数组 hasSentry表示是否有哨兵 0 没有/1 有
void print(int a[], int n, int hasSentry) {
        int i;
        if (hasSentry) {
            for (i = 1; i < n; i++) {
                printf("%d\t", a[i]);
            }
        } else {
            for (i = 0; i < n; i++) 
                printf("%d\t", a[i]);
        }
}