附有本人超級(jí)詳細(xì)解釋?zhuān)床欢拿姹谑欤。?
一、 實(shí)際問(wèn)題:
希爾排序(Shell Sort)是插入排序的一種。因D．L．Shell于1959年提出而得名。它又稱(chēng)“縮小增量分類(lèi)法”，在時(shí)間效率上比插入、比較、冒泡等排序算法有了較大改進(jìn)。能對(duì)無(wú)序序列按一定規(guī)律進(jìn)行排序。
二、數(shù)學(xué)模型:
先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。該方法?shí)質(zhì)上是一種分組插入方法。
三、算法設(shè)計(jì):
1、將相隔某個(gè)增量dlta[k]的元素構(gòu)成一個(gè)子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最后當(dāng)h減到1時(shí)，進(jìn)行一次插入排序，排序就完成。增量序列一般采用：dlta[k]=2t-k+1-1,其中t為排序趟數(shù)，1≤k≤t≤[log2 (n+1)]，其中n為待排序序列的長(zhǎng)度。按增量序列dlta[0..t-1]。
2、按增量dlta[k]（1≤k≤t≤[log2 (n+1)]）進(jìn)行一趟希爾插入排序。
3、在主函數(shù)中控制程序執(zhí)行流程。
4、時(shí)間復(fù)雜度：1≤k≤t≤[log2 (n+1)]時(shí)為O（n3/2）。
標(biāo)簽：
Shell
1959
Sort
排序
上傳時(shí)間：
2013-12-11
上傳用戶(hù)：天涯
