Python Shell排序
Shell排序属于插入排序, 增量为1的Shell排序就是直接插入排序设增量用h表示,Shell排序就是 将数组分为k = (len-1)/h组, 每组为i + n*h 序列 (n为整数 , n=,i= )
即分成序列:
0,h,2*h......
1,1+h , 1+ 2*h.....
2, 2 +h, 2 + 2* h...
....
i , i + h, i +2*h....
分别为这些序列进行插入排序,再重新计算h值排序
增量公式有许多,这里使用 h = 3 * h +1
#Shell排序
class ShellSort:
def sort(self,arrData):
length = len(arrData);
h = 1;
while h < length/3:
h = h*3 +1;
while h>0:
i = h;
while i < length:
if arrData < arrData:
#保存arrData以免被覆盖
tmp = arrData;
j = i - h;
#整体向后移动,
while j>=0 and arrData > tmp:
arrData = arrData;
j = j - h;
arrData = tmp;
i = i + 1;
print(arrData);
h = (h-1)//3;
return;
shellSort = ShellSort();
shellSort.sort();
页:
[1]