NB三人组之 快速排序
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left]
li[left] = tmp # 当left和right都指向同一个角标时
return left def _quick_sort(li, left, right):
if left < right:
mid = partition(li, left, right)
_quick_sort(li, left, mid-1)
_quick_sort(li, mid+1, right) def quick_sort(li):
_quick_sort(li, 0, len(li)-1)
quick_sort
NB三人组之 堆排序
def sift(li, low, high):
i = low
j = 2*i + 1
tmp = li[low]
while j <= high:
if j + 1 <= high and li[j] < li[j+1]:
# j<=high表示如果有两个分支 如果左边孩子小于右边孩子那么交换
j = j+1
if tmp < li[j]:
li[i] = li[j]
i = j
j = i*2 + 1
else:
break
li[i] = tmp def heap_sort(li):
n = len(li)
for i in range(n//2-1, -1, -1):
sift(li, i, n-1)
# 开始出数
for i in range(n-1, -1, -1):
li[i], li[0] = li[0], li[i]
# 现在堆的范围是0 ~ i-1 i的位置用来存放出数的值
sift(li, 0, i-1)
heap_sort
NB三人组之 归并排序
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high:
if li[i] > li[j]:
ltmp.append(li[j])
j += 1
else:
ltmp.append(li[i])
i += 1
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp def merge_sort(li, low, high):
if low < high:
mid = (low + high) // 2
merge_sort(li, low, mid)
merge_sort(li, mid+1, high)
merge(li, low, mid, high)
merge_sort
附加之 希尔排序（插入排序的变种）
def insert_sort_gap(li, gap):
for i in range(1, len(li)): # i是摸到的牌的下标
tmp = li[i]
j = i - gap # j是手里最后一张牌的下标
while j >= 0 and li[j] > tmp: # 两个终止条件：j小于0表示tmp是最小的 顺序不要乱
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp @cal_time
def shell_sort(li):
d = len(li) // 2
while d > 0:
insert_sort_gap(li, d)
d = d // 2