小朋友学数据结构-10大排序算法（2）：直接插入排序

àì夳堔傛蜴生んèń 2022-04-08 10:59 137阅读 0赞

# 一、基本思想 #

在要排序的一组数中，假设前面(n-1)\[n>=2\] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。  
举例：数组a\[\] = \{57, 68, 59, 52\}。  
比较方法是每个数与前面的数比较。  
第一个57，前面没有数，不用比较。  
第二个数68，与前面的57比较，因为68 > 57，所以不用换位置。  
第三个数59，先与前面的68比较，因为59 < 68，所以需要与更前面的数57比较，因为59 > 57。所以无论57的前面有没有数，都不用再比较了。把59插入到57和68之间就可以了。  
第四个数52，前面有三个数：57，59，68。先与68比，52 < 68，需要再与59比，52 < 59，需要再与57比，52 < 57。此时前面没有数了。所以把52插入到57的前面。  
最终的结果为52，57，59，68。

![1.png][]

# 二、代码实现 #

#include<stdio.h>
    
    
    void insertSort(int a[], int n)
    {
        int i, j, temp;
        for (i = 1; i < n; i++)
        {
            temp = a[i];
            j = i;
    
            // 将大于temp的值整体后移一个单位
            while(j > 0 && a[j-1] > temp)
            {
                a[j] = a[j-1];
                j--;
            }
            a[j]=temp;
        }
    }
    
    
    int main()
    {
        int arr[] = {57, 68, 59, 52};
        int len = sizeof(arr) / sizeof(int);
        insertSort(arr, len);
        int i = 0;
        for(; i < len; i++)
        {
            printf("%d ", arr[i]);
        }
    
        return 0;
    }

运行结果：

52, 57, 59, 68

程序分析：  
for循环中，  
（1） i = 1, temp = a\[1\] = 68, j = 1, a\[0\] = 57, a\[0\] > temp不成立，不需要调整

（2）i = 2，temp = a\[2\] = 59，  
① j = 2，a\[1\] = 68 > temp，执行循环a\[2\] = a\[1\] = 68，j自减。  
② j = 1, a\[0\] = 57 > temp不成立，循环结束。  
③ 最后执行a\[1\] = temp = 59，此时arr = \{57，59，68，52\}

（3）i = 3，temp = a\[3\] = 52  
① j = 3, a\[2\] = 68 > temp，执行循环a\[3\] = a\[2\] = 68，j自减  
② j = 2，a\[1\] = 59 > temp，执行循环a\[2\] = a\[1\] = 59，j自减  
③ j = 1，a\[0\] = 57 > temo，执行循环a\[1\] = a\[0\] = 57，j自减后变为0，循环结束  
④ 最后执行a\[0\] = temp = 52，此时a= \{52, 57, 59, 68\}

# 三、时间复杂度分析 #

（一）最好的情况  
最好的情况是数据顺序排列，比如\{1，2，3，4，5\}。比较次数为4次，移动次数为0次。  
若有n个顺序排列的元素，比较次数为n - 1次，移动次数为0。所以复杂度是O(n)。

（二）最坏的情况  
最坏的情况是数据倒序排列，比如\{5，4，3，2，1\}。比较次数为1 + 2 + 3 + 4 = 10次，移动次数2 + 3 + 4 + 5 = 14次。  
若有n个倒序排列的次数，比较次数为 1 + 2 + …… + (n - 1) = n (n - 1) / 2，移动次数为2 + 3 + … + n = (n - 1) (n + 2) / 2。总次数是n (n - 1) / 2 + (n - 1)(n + 2) / 2 = (n - 1) (n + 1)。所以复杂度是O(n2)。

（三）平均情况  
平均情况，比较、移动的次数为最好情况与最坏情况的平均值，即  
\[(n - 1) + (n - 1)(n + 1)\] / 2 = (n - 1) (n + 2) / 2。复杂度为O(n2)。

# 四、稳定性 #

以\{5，2，2，1\}为例，首先是第一个2，插到5的前面，第二个2根据直接插入排序的算法只会插到第一个2和5之间，不会插到第一个2之前。  
所以直接插入排序法是一种稳定的排序算法。

> 想了解更详细的教程，或想了解少儿编程、少儿英语请加微信307591841或QQ307591841  
> ![公众号.jpg][.jpg]

[1.png]: /images/20220406/39cbfb40bb5741e58ccfa4ff71e57b40.png
[.jpg]: /images/20220406/2267000dc679448fa5d78aa0b0fbe295.png