简单插入排序&希尔排序(python)
我不爱机器学习
专注机器学习、数据分析、编程语言，欢迎交流学习
Official Account
简单插入排序
基本思想：
-
当前元素与前一个元素比较，若前一个元素大于当前元素，则前一个元素后移，并用指针记录此时的位置； -
重复此过程，直到找到比其小的元素，则将元素赋给此时指针指向的位置；重复上面两个过程，直到当前元素为最后一个元素； -
注意，当前元素是从前往后开始取，但比较时，是从当前位置向前比较，并用指针记录位置，此时当前元素的前面元素均已排序。
def insertSort(lst):
n = len(lst)
if n <= 1: return lst
# 遍历所有的元素
for i in range(1, n):
cur = lst[i] # 当前元素
j = i - 1 # 位置记录指针
# 当前元素小于前一个元素
while j >= 0 and cur < lst[j]:
lst[j + 1] = lst[j] # 前一个元素往后移
j -= 1
# 此时的j指向前一个元素(前一个元素<=cur)
lst[j + 1] = cur
return lst
lst = input('输入数字：').split(' ')
lst = [eval(x) for x in lst]
insertSort(lst)
希尔排序
基本思想：
-
对不同间隔的元素进行比较，从后向前比较； -
间隔取值为 np.arange(n//2,0,-1)，从大到小进行取值； -
如[3,4,5,2,1]，间隔为2时，5，3比较，2,4比较，1,5比较，1,3比较；间隔为1时，4,3比较，5,4比较，5,3比较......； -
是一个递归过程。
def shellSort(lst):
# start with a big gap,then reduce the gap
n = len(lst)
gap = n // 2
print(lst)
# Do a gapped insertion sort for this gap size.
# The first gap elements lst[0..gap-1] are already in gapped
# order keep adding one more element until the entire array
# is gap sorted
while gap > 0:
for i in range(gap, n):
# save lst[i] in cur and make a hole at position i
cur = lst[i] # 获取当前元素，因为是从后往前比较，因此从gap开始
j = i # 位置记录指针
while j >= gap and lst[j - gap] > cur:
lst[j] = lst[j - gap]
j -= gap
# put cur (the lst[i]) in its correct location
lst[j] = cur
print(lst)
gap = gap // 2
return lst
# -------------------------------------------------------------
# 递归写法
def shellSort(lst):
def sort(lst, gap):
for i in range(gap, n):
cur = lst[i] # 获取当前元素，因为是从后往前比较，因此从gap开始
j = i # 位置记录指针
while j >= gap and lst[j - gap] > cur:
lst[j] = lst[j - gap]
j -= gap
lst[j] = cur
n = len(lst)
gap = n // 2
while gap > 0:
sort(lst, gap)
gap = gap // 2
return lst
lst = input('输入数字：').split(' ')
lst = [eval(x) for x in lst]
shellSort(lst)
总结：都是从前往后遍历，再从后往前比较。