插入排序

插入排序

插入排序是通过交换位置来达到排序的目的的,看起来和选择排序差不多,选择排序是每一次循环都找到一个当前的最小值,然后与第一个元素交换位置,这样从0到N,每一个元素依次排好序。插入排序的不同在于它元素交换的次数是不固定的,如果是一个已经排好序的数组,那么就不会交换,考虑最复杂的情况的话,会交换(1 + 2 + ... + N-1),而选择排序会固定交换N-1次,写到这里,好像选择排序可以优化一下,如果本身是排好序的,那么选择排序也不应该做多余的交换:

if(min != i) {
    int tmp = arr[i];
    arr[i] = arr[min];
    arr[min] = tmp;
}

插入排序的代码如下:

private static void insertSort() {
    int[] arr = {5, 1, 7, 3, 0, 8, 2, 6, 4, 9};
    int N = arr.length;
    for(int i=1; i<N; i++) {
        for(int j=i; j>0 && arr[j] < arr[j-1]; j--) {
            int tmp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = tmp;
        }
    }

    for(int n=0; n<N; n++) {
        System.out.println(arr[n] + " ");
    }
}

对于1到N-1之间的每一个i,将arr[i]与arr[0]到arr[i-1]中比它小的所有元素依次有序地交换,在索引i由左向右变化的过程中,它左侧的元素总是有序的,这样直到排序完成。很显然,对于部分有序的数组来说,插入排序效率要更高一些。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 220,367评论 6 512
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,959评论 3 396
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 166,750评论 0 357
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 59,226评论 1 295
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,252评论 6 397
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,975评论 1 308
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,592评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,497评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,027评论 1 319
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,147评论 3 340
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,274评论 1 352
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,953评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,623评论 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,143评论 0 23
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,260评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,607评论 3 375
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,271评论 2 358

推荐阅读更多精彩内容

  • 算法之插入排序 一:基本概念插入排序(Insert Sort),每次将一个待排序的数据元素,插入到前面已经排好序的...
    墨小飞阅读 269评论 0 0
  • 上一篇博客我们实现的数组结构是无序的,也就是纯粹按照插入顺序进行排列,那么如何进行元素排序,本篇博客我们介绍几种简...
    IT可乐阅读 428评论 0 3
  • 物是人非,只想说一声,感谢你曾经繁华了我的青春!
    放牛的小毛驴阅读 232评论 0 0
  • 很喜欢”我是来搞笑的”专题,一入简书就被它吸引过去了,我自己也写了一些自以为搞笑但没几个人看的文章。哈哈,都...
    糊涂印象阅读 407评论 0 0
  • 言千曦跟傲天回去后,府里寂静了不少。直到夜宴这几天,言千凌本应是很清闲的,但京城却又出了另一桩事,远比慕颐风的盗窃...
    原小尚阅读 282评论 1 1