插入排序法 ，思路详解

1.1. 理解插入排序

插入排序则是比选择排序更为高效排序算法。插入排序排序方式如同图书管理员收到归还的书籍，管理员要找到书籍所在书架，将书籍插入所在位置。

1.2. 插入排序算法原理

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。
1.3. 插入排序实现过程

image.png

1)首先对于待排序数组中第一个元素认定为有序序列，
所以排序从数组中第二个元素开始。

2)第一次进行排序的时候从有序序列中开始查找27的插入位置，27小于53应插入53之前，此时将27提取出来后，将53.后移，再将27放入原53所在位置，便完成了第一次的排序。

3)第二次排序的时候从有序序列中开始查找36的插入位置，36小于53，大于27，36的插入位置在27与53之间，此时将36提取出来后，将53.后移，再将36放入原53所在位置，便完成了第二次的排序。

4)第三次排序的时候从有序序列中开始查找15的插入位置，15小于53、小于36、小于27，15的插入位置在27之前，此时将15提取出来后，将27、36、53.整体向后移动一位，再将15放入原27所在位置，便完成了第三次的排序。

5)第四次排序的时候从有序序列中开始查找69的插入位置，69大于53，69的插入位置在53之后，因此69的位置不需改变，即完成了第四次的排序。

6)第五次排序的时候从有序序列中开始查找42的插入位置，42小于69、小于53、大于36，因此42的插入位置在36之后53之前，此时将42提取出来后，将53.、69整体向后移动一位，再将42放入原53所在位置，便完成了第五次的排序。

7)此时整个数组均为有序排列。

下面是插入排序的代码：
核心步骤
第一步-比较num[0]和num[1]的大小，如果num[0]大就交换位置，保证从小到大排好
第二步-每一轮拿num[i]和num[0~i]之间的数字进行比较，保证num[i]插入左边的数组后，左边的数组从小到大排好顺序。

#include <stdio.h>
 
int main(){
    //插入排序
    int num[10] = {3,0,1,8,7,2,5,4,9,6};
    
    for(int i = 0; i < 10-1; i++){//控制次数 
        //判断i和i+1的大小
        if(num[i] > num[i+1]){
            //换位置
            int temp = num[i];
            num[i] = num[i+1];
            num[i+1] = temp;
            
            //让i对应的值和前面所有的值进行比较
            for (int j = i; j > 0; j--){
                //j和j-1进行比较
                if(num[j] > num[j-1]){
                    //当前这个位置就是这个数字的位置 
                    break;
                } else{
                    //j和j-1换位置
                    int temp = num[j];
                    num[j] = num[j-1];
                    num[j-1] = temp; 
                } 
            } 
        } 
    } 
    
    //输出
    for(int i = 0; i < 10; i++){
        printf("%d ", num[i]);
    } 
    return 0;
}