算法基础：排序算法：插入排序

た入场券 2022-12-18 06:56 187阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
插入排序也是非常容易理解的排序算法，这篇文章介绍一下排序的主要要点和实现，插入排序的主要做法是外层循环中选定插入元素，内层循环移动并空出插入位置，返回外层循环进行插入。

### 目录 ###

*  算法思路
 *  算法要点
 *  模拟实现
 *  结果验证

--------------------

# 算法思路 #

>  *  插入排序在理解上可以参考打牌时的同花顺的单手排序过程，插入只是算法的一个重要动作，另外还有一个动作就是选择，如果将插入排序理解为元素从1到N的一个初始化过程，每次插入之后保证当前的序列是已排序的也没有问题，但是这种情况需要而外的一个O（n）的空间，相较于冒泡排序和选择排序的交换，插入排序的特点在于后移和插入。首先将外层循环的当前元素保存在一个额外的变量之中，内层循环显著的特点是在已排序的序列中进行循环，根据要插入的元素和已排序的元素进行比较，决定移位。然后在外层循环中进行插入。

--------------------

# 算法要点 #

选择排序的主要要点如下所示(N个元素，数组元素从0开始计数)：

*  外层循环：1 <= i <=N - 1 (N-1次循环) 递加方式循环即可，第一个元素可以认为是有序的。
 *  插入选择：每次当前元素均为选择元素v，需要将其保存起来，这个辅助变量是必须的，它是内层循环移动的前提和保证。
 *  内层循环：内层循环下标从i-1开始（表示已经排序的序列部分），倒序至j >= 0,
 *  移位：在内层循环中满足\[j\] < v 和 j>=0的条件下进行后移操作，因为插入选择中的元素v为已经保存，而此元素为内层循环开始的最大值+1，所以可以直接顺次后移，这是插入算法最核心需要理解的内容
 *  插入：内层循环不满足条件时，退出之后，在外层循环中将之前的输入选择保存的v插入进去即可（注意内层循环多减了一次，下标需要加回）

# 模拟实现 #

void insert_sort(int* arr, int num) { 
        for (int i=1; i<num; i++) { 
            int value = arr[i], j=i-1;
            for (j=i-1; j>=0 && arr[j] > value; j--) arr[j+1] = arr[j];
            arr[++j] = value;
        }
    }

--------------------

# 结果验证 #

加上打印和调用的示例代码，可以使用如下方式进行验证

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    void insert_sort(int* arr, int num) { 
        for (int i=1; i<num; i++) { 
            int value = arr[i], j=i-1;
            for (j=i-1; j>=0 && arr[j] > value; j--) arr[j+1] = arr[j];
            arr[++j] = value;
        }
    }
    
    void print_array(int* arr, int num) { 
        for (int i=0; i<num; i++) printf("%d ",arr[i]);
        printf("\n");
    }
    
    int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) { 
                scanf("%d",&array[i]);
            }
            insert_sort(array,n);
            print_array(array,n);
            free(array); array= NULL;
        }
    }

执行结果示例

8
    9 8 7 6 5 4 3 2
    2 3 4 5 6 7 8 9

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/ec166165427748ccad8f29609758564b.png