天天看點

經典算法題每日演練——第二十四題 梳排序

  這篇再看看一個經典的排序,梳排序,為什麼取名為梳,可能每個梳都有自己的gap吧,大梳子gap大一點,小梳子gap小一點。

上一篇我們看到雞尾酒排序是在冒泡排序上做了一些優化,将單向的比較變成了雙向,同樣這裡的梳排序也是在冒泡排序上做了一些優化。

冒泡排序上我們的選擇是相鄰的兩個數做比較,就是他們的gap為1,其實梳排序提出了不同的觀點,如果将這裡的gap設定為一定的大小,

效率反而必gap=1要高效的多。

 下面我們看看具體思想,梳排序有這樣一個1.3的比率值,每趟比較完後,都會用這個1.3去遞減gap,直到gap=1時變成冒泡排序,這種

算法比冒泡排序的效率要高效的多,時間複雜度為o(n2/2p)  這裡的p為增量,是不是跟希爾排序有點點神似。。。

    比如下面有一組資料: 初始化的gap=list.count/1.3, 然後用這個gap作為數組下标進行跨數字比較大小,前者大于後者則進行交換,

每一趟排序完成後都除以1.3, 最後一直除到gap=1

經典算法題每日演練——第二十四題 梳排序

最後我們的數組就排序完畢了,下面看代碼:

經典算法題每日演練——第二十四題 梳排序

繼續閱讀