左神算法數(shù)據(jù)結(jié)構(gòu)體系學(xué)習(xí)班
希爾排序
算法思想：
希爾排序的算法思想：將待排序數(shù)組按照步長gap進(jìn)行分組（已報(bào)名左程云算法 底部評），然后將每組的元素利用直接插入排序的方法進(jìn)行排序；每次將gap折半減小，循環(huán)上述操作；當(dāng)gap=1時(shí)，利用直接插入，完成排序。
同樣的：從上面的描述中我們可以發(fā)現(xiàn)：希爾排序的總體實(shí)現(xiàn)應(yīng)該由三個循環(huán)完成：
第一層循環(huán)：將gap依次折半，對序列進(jìn)行分組，直到gap=1
第二、三層循環(huán)：也即直接插入排序所需要的兩次循環(huán)。具體描述見上。
代碼實(shí)現(xiàn)：
#希爾排序def insert_shell(L):
? ?#初始化gap值，此處利用序列長度的一般為其賦值
? ?gap = (int)(len(L)/2) ? ?#第一層循環(huán)：依次改變gap值對列表進(jìn)行分組
? ?while (gap >= 1): ? ?#下面：利用直接插入排序的思想對分組數(shù)據(jù)進(jìn)行排序
? ?#range(gap,len(L)):從gap開始
? ? ? ?for x in range(gap,len(L)): ? ?#range(x-gap,-1,-gap):從x-gap開始與選定元素開始倒序比較，每個比較元素之間間隔gap
? ? ? ? ? ?for i in range(x-gap,-1,-gap): ? ?#如果該組當(dāng)中兩個元素滿足交換條件，則進(jìn)行交換
? ? ? ? ? ? ? ?if L[i] > L[i+gap]:
? ? ? ? ? ? ? ? ? ?temp = L[i+gap]
? ? ? ? ? ? ? ? ? ?L[i+gap] = L[i]
? ? ? ? ? ? ? ? ? ?L[i] =temp ? ?#while循環(huán)條件折半
? ? ? ?gap = (int)(gap/2)
