先取一個小于n的整數(shù)d1作為第一個增量,把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序;然后,取第二個增量d2<d1重復(fù)上述的分組和排序,直至所取的增量dt=1(dt<dt-l<;…<d2<d1),即所有記錄放在同一組中進行直接插入排序為止。
該方法實質(zhì)上是一種分組插入方法。
原理圖:
源代碼
運行結(jié)果:
Shell排序是不穩(wěn)定的,它的空間開銷也是O(1),時間開銷估計在O(N3/2)~O(N7/6)之間
新聞熱點
疑難解答
圖片精選