排序算法之插入排序

待我称王封你为后i 2022-06-16 07:48 184阅读 0赞

问题描述：

输入一个原始数列，把它进行升序排序，从小到大输出。

例如：给定数列如下：  
5 15 99 45 12 1 90 19 33 41

排序后的结果为：  
1 5 12 15 19 33 41 45 90 99

插入排序，就是从第二个数开始（因为第一个数肯定是排好了的），如果比前面的数大，那就什么都不用做，因为已经有序了，如果比前面的小，往前面进行查找，寻找合适的位置进行插入，每个数都进行这样的操作，那么进行N-1次之后数列就会变得有序了，下面我们来看一下具体的过程：

下标值序号： 0 1 2 3 4 5 6 7 8 9  
原始状态为： 5 15 99 45 12 1 90 19 33 41  
第一趟排序： 5 15 99 45 12 1 90 19 33 41 （15比5要大不需要动）  
第二趟排序： 5 15 99 45 12 1 90 19 33 41（99比15要大不需要动）  
第三趟排序： 5 15 45 99 12 1 90 19 33 41（45比99要小，往前面找到合适的位置插入）  
第四趟排序： 5 12 15 45 99 1 90 19 33 41（12比99要小，往前面找到合适的位置插入）  
第五趟排序： 1 5 12 15 45 99 90 19 33 41（1比99要小，往前面找到合适的位置插入）  
第六趟排序： 1 5 12 15 45 90 99 19 33 41（90比99要小，往前面找到合适的位置插入）  
第七趟排序： 1 5 12 15 19 45 90 99 33 41（19比99要小，往前面找到合适的位置插入）  
第八趟排序： 1 5 12 15 19 33 45 90 99 41（33比99要小，往前面找到合适的位置插入）  
第九趟排序： 1 5 12 15 19 33 41 45 90 99（41比99要小，往前面找到合适的位置插入）

从上面我们可以发现：  
1. 对于N个数的数列来说，需要N-1趟才能完全排好  
2. 插入排序只要当后面比前面小的时候才需要去插入，否则不用动  
3. 也就是说最好的情况，时间复杂度是O（n）的，那就是本来就全部有序  
4. 该算法在越有序的情况下，速度越快  
5. 算法的平均时间复杂度是O（n^2）

参考代码：

#include<stdio.h>
    
    int main()
    {
        int arr[] = { 5, 15, 99, 45, 12, 1, 90, 19, 33, 41 };
        int i, j, nTemp, nCount = sizeof(arr) / sizeof(arr[0]);
        printf("排序前\n");
        for (i = 0; i < nCount; i++)
            printf("%d ", arr[i]);
        printf("\n");
    
        for (i = 1; i < nCount; i++)
        {
            if (arr[i] < arr[i - 1])//如果后面的数比前面的数要小，再去找合适的位置插入，否则已经有序了
            {
                nTemp = arr[i];
                for (j = i - 1; nTemp < arr[j]; j--)
                    arr[j + 1] = arr[j];
                arr[j + 1] = nTemp;
            }
        }
    
        printf("\n排序后\n");
        for (i = 0; i < nCount; i++)
            printf("%d ", arr[i]);
        printf("\n");
        return 0;
    }

运行结果：

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220616/fcf71db2605b45ae8bad999140e77765.png