CExercise_13_1排序算法_1插入排序

题目：

请自己手动实现插入排序算法：

// 插入排序 void insertion_sort(int arr[], int len);
然后给定一个int数组，实现将它从小到大进行排序。

关键点

分析：

在插入排序中，稳定性指的是排序算法能够保持相等元素的原始相对顺序不变。也就是说，如果原始数组中有两个相等的元素 A 和 B，且 A 出现在 B 之前，那么在排序后，A 仍然应该在 B 之前。

代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ARR_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
/*
    插入排序 void insertion_sort(int arr[], int len);
    然后给定一个int数组，实现将它从小到大进行排序
*/

// 打印数组函数
void print_arr(int arr[], int len) {
    for (int i = 0; i < len; i++) {//数组的长度len-1,下标从0开始.
        printf("%d ", arr[i]);
    }
    printf("\n");
}
void insertion_sort(int arr[], int len) {
    //从第二个元素开始比,因为只有一个元素的话默认有序.
    for (int i = 1;i < len;i++) {//外层for循环代表每一轮摸到的新手牌,也就是每一轮插入排序.
        int temp = arr[i];
        int j = i - 1;//下标j代表左边的元素.
        for (;j >= 0;j--) {

            if (arr[j] > temp) {//注意:不能加=,加了就不是稳定排序算法了
                arr[j + 1] = arr[j];
            }
            else {
                break;//只要发现一个更小和相等,说明找到插入位置了
            }
        }
//for循环结束的两种情况:1)j=-1时,循环结束,说明该数最小,所以插入到0这个位置,也就是j+1;
        //2)arr[j]<=temp 原本的数更小或相等,此时手牌放在j+1的位置
        arr[j + 1] = temp;
        print_arr(arr, len); //每一轮摸牌后查看排序后的数组
    }
}


int main(void) {
    int arr[] = { 1,46,6,5,7,8,55,7,23,65,6 };
    int len = ARR_SIZE(arr);
    insertion_sort(arr, len);
    return 0;
}
	

解决方案总结：

：