排序三直接插入排序


要点

直接插入排序是一种最简单的插入排序

插入排序:每一趟将一个待排序的记录,按照其关键字的大小插入到有序队列的合适位置里,知道全部插入完成。

在讲解直接插入排序之前,先让我们脑补一下我们打牌的过程。

先拿一张5在手里,

再摸到一张4,比5小,插到5前面,

摸到一张6,嗯,比5大,插到5后面,

摸到一张8,比6大,插到6后面,

。。。

最后一看,我靠,凑到全是同花顺,这下牛逼大了。

以上的过程,其实就是典型的直接插入排序,每次将一个新数据插入到有序队列中的合适位置里

很简单吧,接下来,我们要将这个算法转化为编程语言。

假设有一组无序序列 R0, R1, ... , RN-1。

(1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。

(2) 然后,我们要依次把 R1, R2, ... , RN-1 插入到这个有序序列中。所以,我们需要一个外部循环,从下标 1 扫描到 N-1 。

(3) 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述,我们可知,插入Ri时,前 i-1 个数肯定已经是有序了。

所以我们需要将Ri 和R0 ~ Ri-1 进行比较,确定要插入的合适位置。这就需要一个内部循环,我们一般是从后往前比较,即从下标 i-1 开始向 0 进行扫描。

核心代码

public voidinsertSort(int[]list){
 //打印第一个元素
 System.out.format("i=%d:	",0);
 printPart(list,0,0);
 
 //第1个数肯定是有序的,从第2个数开始遍历,依次插入有序序列
  for(inti=1;i<list.length;i++){
 intj=0;
 inttemp=list[i];//取出第i个数,和前i-1个数比较后,插入合适位置
 
 //因为前i-1个数都是从小到大的有序序列,所以只要当前比较的数(list[j])比temp大,就把这个数后移一位
  for(j=i-1;j>=0&&temp<list[j];j--){
 list[j+1]=list[j];
 }
 list[j+1]=temp;
 
 System.out.format("i=%d:	",i);
 printPart(list,0,i);
 }
 }

算法分析

直接插入排序的算法性能

时间复杂度

当数据正序时,执行效率最好,每次插入都不用移动前面的元素,时间复杂度为O(N)

当数据反序时,执行效率最差,每次插入都要前面的元素后移,时间复杂度为O(N2)

所以,数据越接近正序,直接插入排序的算法性能越好

空间复杂度

由直接插入排序算法可知,我们在排序过程中,需要一个临时变量存储要插入的值,所以空间复杂度为 1

算法稳定性

直接插入排序的过程中,不需要改变相等数值元素的位置,所以它是稳定的算法。

完整参考代码

JAVA版本

代码实现

1 packagenotes.javase.algorithm.sort;
 2 
 3 importjava.util.Random;
 4 
 5 public classInsertSort{
 6 
 7 public voidinsertSort(int[]list){
 8 //打印第一个元素
 9System.out.format("i=%d:	",0);
 10printPart(list,0,0);
 11 
 12 //第1个数肯定是有序的,从第2个数开始遍历,依次插入有序序列
 13 for(inti=1;i<list.length;i++){
 14 intj=0;
 15 inttemp=list[i];//取出第i个数,和前i-1个数比较后,插入合适位置
 16  
 17  //因为前i-1个数都是从小到大的有序序列,所以只要当前比较的数(list[j])比temp大,就把这个数后移一位
 18 for(j=i-1;j>=0&&temp<list[j];j--){
 19list[j+1]=list[j];
 20}
 21list[j+1]=temp;
 22 
 23System.out.format("i=%d:	",i);
 24printPart(list,0,i);
 25}
 26}
 27 
 28 //打印序列
 29 public voidprintPart(int[]list,intbegin,intend){
 30 for(inti=0;i<begin;i++){
 31System.out.print("	");
 32}
 33 for(inti=begin;i<=end;i++){
 34System.out.print(list[i]+"	");
 35}
 36System.out.println();
 37}
 38 
 39 public static voidmain(String[]args){
 40 //初始化一个随机序列
 41 final intMAX_SIZE=10;
 42 int[]array=new int[MAX_SIZE];
 43Randomrandom=newRandom();
 44 for(inti=0;i<MAX_SIZE;i++){
 45array[i]=random.nextInt(MAX_SIZE);
 46}
 47 
 48 //调用冒泡排序方法
 49InsertSortinsert=newInsertSort();
 50System.out.print("排序前:	");
 51insert.printPart(array,0,array.length-1);
 52insert.insertSort(array);
 53System.out.print("排序后:	");
 54insert.printPart(array,0,array.length-1);
 55}
 56}

运行结果

排序前:6335631064
 i=0:6
 i=1:36
 i=2:336
 i=3:3356
 i=4:33566
 i=5:333566
 i=6:1333566
 i=7:01333566
 i=8:013335666
 i=9:0133345666
 排序后:0133345666 

参考资料

《数据结构习题与解析》(B级第3版)

http://www.cnblogs.com/huangxincheng/archive/2011/11/20/2255695.html

相关阅读

欢迎阅读 程序员的内功——算法 系列

示例源码:https://github.com/dunwu/algorithm-notes

优质内容筛选与推荐>>
1、C#基类和派生类(转)
2、探密诡异的HTTP Referer总是为空的原因 --- 转自 本园的陈力就列崇论闳议
3、索引的作用及优缺点
4、hdu 1538 A Puzzle for Pirates 博弈论
5、Html/Css基础学习一(基础标签)


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号