def sort(arr):
h = 1
size = len(arr)
while h < size // 3:
h = 3 * h + 1
while h >= 1:
for i in range(h, size):
j = i
while j >= h and arr[j] < arr[j-h]:
tmp = arr[j-h]
arr[j-h] = arr[j]
arr[j] = tmp
j -= h
h = h // 3
return arr
歸并排序
代碼實現(xiàn)
# coding=utf-8
###歸并排序
class Merge:
# 額外數(shù)組空間
aux = []
def sort(self, arr):
count = len(arr)
##初始化數(shù)據(jù)大小
self.aux = [0] * count
self.sort0(arr, 0, count - 1)
def sort0(self, arr, low, high):
if low < high:
mid = (low + high) // 2
self.sort0(arr, low, mid)
self.sort0(arr, mid + 1, high)
self.merge(arr, low, mid, high)
def merge(self, arr, low, mid, high):
for i in range(low, high + 1):
self.aux[i] = arr[i]
i = low
j = mid + 1
#原地歸并
for k in range(low, high + 1):
if i > mid:
arr[k] = self.aux[j]
j += 1
elif j > high:
arr[k] = self.aux[i]
i += 1
elif self.aux[j] >= self.aux[i]:
arr[k] = self.aux[i]
i += 1
else:
arr[k] = self.aux[j]
j += 1
