00 序
排序算法有多种(不限定应用场景,可有10种以上),今天实现了其中的8种:
01 冒泡排序
def bubble_sort(lyst):
for i in range(len(lyst)):
for j in range(len(lyst)-1, i, -1):
if lyst[j] < lyst[j-1]:
lyst[j], lyst[j-1] = lyst[j-1], lyst[j]
02 选择排序
def select_sort(lyst):
for i in range(len(lyst)):
minIndex = i
for j in range(i+1,len(lyst)):
if lyst[j] < lyst[minIndex]:
minIndex = j
lyst[i], lyst[minIndex] = lyst[minIndex], lyst[i]
03 插入排序
def insert_sort(lyst):
for i in range(1, len(lyst)):
j, temp = i-1, lyst[i]
while j >= 0 and lyst[j] > temp:
lyst[j+1], j = lyst[j], j-1
lyst[j+1] = temp
04 希尔排序
def shell_sort(lyst):
gap = len(lyst)//2
while gap:
for i in range(gap, len(lyst)):
j, temp = i-gap, lyst[i]
while j >= 0 and lyst[j] > temp:
lyst[j+gap], j = lyst[j], j-gap
lyst[j+gap] = temp
gap //= 2
05 归并排序
def merge_sort(lyst):
if len(lyst) <= 1:
return lyst
left = merge_sort(lyst[:len(lyst)//2])
right = merge_sort(lyst[len(lyst)//2:])
l = r = index = 0
while l<len(left) and r<len(right):
if left[l] <= right[r]:
lyst[index], l = left[l], l+1
else:
lyst[index], r = right[r], r+1
index += 1
lyst[index:] = left[l:] if l<len(left) else right[r:]
return lyst
06 快速排序(2种实现)
def quick_sort(lyst):
def quick_helper1(lyst, left, right):
"""快慢指针确定分界,其中slow表示下区间的右界, left,right为左闭右开区间"""
if left >= right-1:
return
pivot = left
slow = left
for fast in range(left+1, right):
if lyst[fast] <= lyst[pivot]:
slow += 1
lyst[fast], lyst[slow] = lyst[slow], lyst[fast]
lyst[pivot], lyst[slow] = lyst[slow], lyst[pivot]
quick_helper1(lyst,left, slow)
quick_helper1(lyst, slow+1, right)
def quick_helper2(lyst, left, right):
"""左右指针确定分界,其中l或l-1表示下区间的右界, left,right为左闭右开区间"""
if left >= right-1:
return
pivot = left
l, r = left+1, right-1
while l < r:
if lyst[l] <= lyst[pivot]:
l += 1
elif lyst[r] > lyst[pivot]:
r -= 1
else:
lyst[l], lyst[r] = lyst[r], lyst[l]
l += 1
r -= 1
if lyst[l] > lyst[pivot]:#确定实际分界
l -= 1
lyst[pivot], lyst[l] = lyst[l], lyst[pivot]
quick_helper2(lyst,left,l)
quick_helper2(lyst, l+1, right)
quick_helper1(lyst, 0, len(lyst))
07 堆排序
def heap_sort(lyst):
def max_heapify(lyst, i, length):
l, r = 2*i+1, 2*i+2
maxIndex = i
if l<length and lyst[maxIndex]<lyst[l]:
maxIndex = l
if r<length and lyst[maxIndex]<lyst[r]:
maxIndex = r
if maxIndex != i:
lyst[i], lyst[maxIndex] = lyst[maxIndex], lyst[i]
max_heapify(lyst, maxIndex, length)
def build_heap(lyst):
for i in range(len(lyst)//2,-1,-1):
max_heapify(lyst, i, len(lyst))
build_heap(lyst)
for i in range(len(lyst)-1,0,-1):
lyst[0], lyst[i] = lyst[i], lyst[0]
max_heapify(lyst, 0, i)
08 记数排序
def count_sort(lyst):
maxValue = max(lyst)
minValue = min(lyst)
counts = [0]*(maxValue - minValue + 1)
for num in lyst:
counts[num-minValue] += 1#将取值归一到 min--max之间
cur = 0
for index, count in enumerate(counts):
if not count:
continue
lyst[cur:cur+count] = [index+minValue]*count
cur += count
09 测试程序及结果
if __name__ == '__main__':
lyst = list(range(1,10001))
from random import shuffle
shuffle(lyst)
import time
sorts = [bubble_sort, select_sort, insert_sort, shell_sort, merge_sort, quick_sort, heap_sort, count_sort]
for sort in sorts:
start = time.time()
sort(lyst[:])
print(f"Time used by {sort.__name__}:", time.time()-start)
"""
Time used by bubble_sort: 10.221662282943726
Time used by select_sort: 3.8268022537231445
Time used by insert_sort: 4.620638608932495
Time used by shell_sort: 0.057811737060546875
Time used by merge_sort: 0.054853200912475586
Time used by quick_sort: 0.028922557830810547
Time used by heap_sort: 0.07084536552429199
Time used by count_sort: 0.004951953887939453
"""
10 下篇计划