程序猿修仙之路--算法之希尔排序

     

           

           

IT

江

湖          

       自冯诺依曼开启大计算机时代以来，经过近一个世纪的蓬勃发展，已然成为一个人才众多的群体：IT江湖            

        依附市场规律，江湖上悄然兴起数十宗门，其中以AI，大数据近期最为热门。每个宗门人才济济，抢夺人才大战早已在阿里，腾讯，百度等数百个国度白热化。            

      IT江湖人士凭借JAVA，Python等武器，在精通各路内功心法的基础上在各个国度扬名立万，修仙成佛者众多，为后人树下追宠之榜样。            

    内功心法众多，其中以算法最为精妙，是修仙德道必经之路。            

       

               

虽然江湖上算法内功繁多，但是好的算法小编认为必须符合以下几个条件，方能真正提高习练者实力：

1            

时间复杂度（运行时间）        

       在算法时间复杂度维度，我们主要对比较和交换的次数做对比，其他不交换元素的算法，主要会以访问数组的次数的维度做对比。。            

        其实有很多修炼者对于算法的时间复杂度有点模糊，分不清什么所谓的 O(n),O(nlogn),O(logn)...等，也许下图对一些人有一些更直观的认识。   

2            

空间复杂度（额外的内存使用）        

    排序算法的额外内存开销和运行时间同等重要。 就算一个算法时间复杂度比较优秀，空间复杂度非常差，使用的额外内存非常大，菜菜认为它也算不上一个优秀的算法。

3            

结果的正确性        

    这个指标是菜菜自己加上的，我始终认为一个优秀的算法最终得到的结果必须是正确的。就算一个算法拥有非常优秀的时间和空间复杂度，但是结果不正确，导致修炼者经脉逆转，走火入魔，又有什么意义呢？
           

   

               

    算法虽然精妙，但需循序渐进修炼，并且需要一定的数学内功基础方可彻底领悟。今日习练算法第三章：排序之希尔排序。

气运丹田 开启修炼之路

           

心法简介    

    上一篇我们修炼了插入排序，希尔排序（又名Shell's Sort）本质上属于插入排序，是插入排序的一种更高效升级版本，也称为**缩小增量排序**。同时希尔排序在时间复杂度上也是突破O(n²）的第一批算法之一。你说厉不厉害？~~