美文网首页互联网科技C++数据结构和算法分析
小朋友学数据结构-10大排序算法(2):直接插入排序

小朋友学数据结构-10大排序算法(2):直接插入排序

作者: 海天一树X | 来源:发表于2018-12-10 16:39 被阅读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

    相关文章

      网友评论

        本文标题:小朋友学数据结构-10大排序算法(2):直接插入排序

        本文链接:https://www.haomeiwen.com/subject/uvhdhqtx.html