1.冒泡排序,T(n) = O(n**2)
# 冒泡排序,T(n) = O(n**2)
def bubble_sort(li):
print(li)
for i in range(len(li)-1): # i代表第几趟
for j in range(len(li) - i - 1): # j代表每趟过程中的下标
if li[j] > li[j + 1]:
li[j], li[j +1] = li[j + 1], li[j]
print(li)
return li
# bubble_sort([9,8,7,6,5,4,3,2,1])
2.选择排序,T(n) = O(n**2)
# 选择排序
def select_sort(li):
for i in range(len(li)-1):
min_index = i
for j in range(i, len(li)):
if li[j] < li[min_index]:
min_index = j
li[i],li[min_index] = li[min_index], li[i]
return li
# print(select_sort([1,9,2,8,3,6,4,5,7]))
3.插入排序,T(n) = O(n**2)
# 插入排序,
def insert_sort(li):
for i in range(1, len(li)): # i代表每次摸到的牌的下标
tmp = li[i]
j = i - 1 # j代表手里最后一张牌的下标
while True:
if j < 0 or tmp >= li[j]:
break
li[j + 1] = li[j]
j -= 1
li[j + 1] = tmp
return li
4.快速排序,T(n) = O(nlogn)
# 快速排序
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 partition(data, left, right):
tmp = data[left]
while left < right:
while left < right and data[right] >= tmp:
right -= 1
data[left] = data[right] # 第一次不满足条件时,right值固定
while left < right and data[left] <= tmp:
left += 1
data[right] = data[left]
data[left]=tmp
return left
print(quick_sort(li, 0, len(li)-1))
print(li)
5.堆排序,T(n) = O(nlogn)
# 堆排序
def sift(data, low, high):
"""
调整函数
data: 列表
low:待调整的子树的根位置
high:待调整的子树的最后一个节点的位置
"""
i = low
j = 2 * i + 1
tmp = data[i]
# i指向空位置
while j<=high: #领导已经撸到底了
if j != high and data[j] < data[j+1]:
j += 1
#j指向数值大的孩子
if tmp < data[j]: #如果小领导比撸下来的大领导能力值大
data[i] = data[j]
i = j
j = 2*i+1
else:
break #撸下来的领导比候选的领导能力值大
data[i] = tmp
def heap_sort(data):
n = len(data)
# 建堆
for i in range(n//2-1, -1, -1):
sift(data, i, n - 1)
# 挨个出数
for high in range(n - 1, -1, -1):
data[0], data[high] = data[high], data[0]
sift(data, 0, high - 1)
6.归并排序,T(n) = O(nlogn)
# 归并排序
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[i])
i += 1
else: # li[i]>li[j]
ltmp.append(li[j])
j += 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 mergesort(li, low, high):
if low < high:
mid = (low + high) // 2
mergesort(li, low, mid)
mergesort(li, mid+1, high)
merge(li, low, mid, high)
7.希尔排序
TODO...
8.基数排序
TODO
网友评论