# Python数据结构与算法（六）—– 希尔排序和快速排序

756-周同学

, , ,

## 排序与算法

### 1. 希尔排序

def shell_sort(alist):
'''shell sort'''
#n=9
n = len(alist)
#gap=4
gap = n // 2
# gap变化到0之前，插入算法执行的次数
while gap >= 1:
# 插入算法，与普通的插入算法的区别就是gap步长
for j in range(gap, n):
# j=(gap,gap+1,gap+2,...)
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的步长
gap //= 2

if __name__ == '__main__':
li = [54,26,93,17,77,31,44,55,20]
print(li)
shell_sort(li)
print(li)


### 2. 快速排序

def quick_sort(alist,first,last):
'''快速排序'''
if first >= last:
return

mid_value = alist[first]
low = first
high = last

while low < high:
# high 左移
while low < high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]

while low < high and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
# 从循环退出时，low == high
alist[low] = mid_value

# 对low左边的列表执行快速排序
quick_sort(alist,first,low-1)
# 对low右边的列表执行快速排序
quick_sort(alist,low+1,last)

if __name__ == '__main__':
li = [54,26,93,17,77,31,44,55,20]
print(li)
quick_sort(li,0,len(li)-1)
print(li)


Vieu3.3主题

Q Q 登 录