图解插入排序中的直接插入排序(秒懂)

作者:包包大人   时间:2018-01-19 11:21:20   来源:原创   阅读:356   评论:0  

直接插入排序的基本思想是 : 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。
第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。
插入排序的基本方法是:每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置,直到全部记录插入完毕为止。
第一趟比较示图:

算法实现:

public static void insertsort(int arr[]){                
        for(int i = 1;i < arr.length; i ++){
            if(arr[i] < arr[i-1]){//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]还大则无需再与[i-1]前面的元素进行比较了,反之则进入if语句
                int temp = arr[i];
                int j;
                for(j = i-1; j >= 0 && arr[j] > temp; j --){                
                        arr[j+1] = arr[j];//把比temp大或相等的元素全部往后移动一个位置            
                }
                arr[j+1] = temp;//把待排序的元素temp插入腾出位置的(j+1)
            }            
        }

    }

    public static void main(String[] args) {
        int array[] = {4,2,1,5};

        System.out.println("排序之前:");
        for(int element : array){
            System.out.print(element+" ");
        }

        insertsort(array);
        System.out.println("\n排序之后:");        
        for(int element : array){
            System.out.print(element+" ");
        }
    }
}

结果:

排序之前:
4 2 1 5
排序之后:
1 2 4 5

算法分析:
1.当元素的初始序列为正序时,仅外循环要进行n-1趟排序且每一趟只进行一次比较,没有进入if语句不存在元素之间的交换(移动)。此时比较次数(Cmin)和移动次数(Mmin)达到最小值。
Cmin = n-1 Mmin = 0;
此时时间复杂度为O(n)。

2.当元素的初始序列为反序时,每趟排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移(arr[j+1] = arr[j]),i个元素后移移动次数当然也就为i了,再加上temp = arr[i]与arr[j+1] = temp的两次移动,每趟移动的次数为i+2,此时比较次数(Cmin)和移动次数(Mmin)达到最小值。

Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2)
Mmax = (1+2)+(2+2)+...+(n-1+2) = (n-1)*(n+4)/2 = O(n2)  (i取值范围1~n-1)

此时时间复杂度为O(n2)。
3.在直接插入排序中只使用了i,j,temp这3个辅助元素,与问题规模无关,所以空间复杂度为O(1).
4.在整个排序结束后,即使有相同元素它们的相对位置也没有发生变化,
如:5,3,2,3排序过程如下

A—3,5,2,3
B—2,3,5,3
C—2,3,3,5

排序结束后两个元素3的相对位置没有发生改变,所以直接插入排序是一种稳定排序。
另附PHP版本:

<?php

//直接插入排序

function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

function InsertSort(array &$arr){
    $count = count($arr);
    //数组中第一个元素作为一个已经存在的有序表
    for($i = 1;$i < $count;$i ++){
        $temp = $arr[$i];      //设置哨兵
        for($j = $i - 1;$j >= 0 && $arr[$j] > $temp;$j --){
            $arr[$j + 1] = $arr[$j];       //记录后移
        }
        $arr[$j + 1] = $temp;      //插入到正确的位置
    }
}

$arr = array(9,1,5,8,3,7,4,6,2);
InsertSort($arr);
var_dump($arr);

插入排序过程动画:

  • 点赞
  • 收藏
  • 分享

评论 (0人参与

最新评论
暂无评论
写博客