希尔排序:
1、将列表以一定间隔 gap 进行划分,再对划分后的每一部分进行插入排序,使
得每一部分构成一个有序的序列
2、再缩小 gap,重复步骤 1,直至 gap = 1,进行最后一次插入排序,获得整
体的有序序列
notes:list 内部操作,无需另外请求地址
# coding:utf-8
# 希尔排序
def shell_sort(alist):
'''希尔排序'''
n = len(alist)
gap = n // 2
while gap > 0:
for j in range(gap, n):
i = j
while i > 0:
if alist[i] < alist[i - gap]:
alist[i], alist[i - gap] = alist[i - gap],
alist[i]
i -= gap
else:
break
gap //= 2
快速排序:将列表通过选定的参考基准分为左/右两部分,左边的都比基准小,
右边的都比基准大,再对左/右的列表进行快排(递归),直至有序排列
快速排序的过程很复杂,中间有多次递归,要注意每次递归时传入的参数是多
过程参考下图:
单次递归的结果是将列表以基准分为小于基准部分和大于基准部分
进行下一次递归时,则将基准左右的数据以新基准进行再次进行划分