常用排序
2020-12-30 本文已影响0人
warManHy
- 冒泡
def pp(list):
n = len(list)
for i in range(n):
for j in range(n-i-1):
if list[j] > list[j+1]:
list[j], list[j+1] = list[j+1],list[j]
- 快排
def sort(arr):
if len(arr) < 2:
return arr
flag = arr[0]
big = [x for x in arr if x > flag]
same = [x for x in arr if x == flag]
small = [x for x in arr if x < flag]
return sort(big) + same + sort(small)
- 插入
def insertSort(list):
n = len(list)
for i in range(n):
tmp = list[i]
j = i - 1
print "out", list, j, tmp
while j >= 0 and list[j] > tmp:
# print list
list[j+1] = list[j] #换值
print list,j
# list[j],list[j+1] = list[j+1], list[j]
j = j - 1
arr[j+1] = tmp #换值
print "fin", list,tmp
- 选择
def selectSort(arr):
n = len(arr)
for i in range(n):
tmp = i
for j in range(i+1, n):
if arr[j] < arr[tmp]:
tmp = j
arr[i], arr[tmp] = arr[tmp], arr[i]
- 归并(分治)
随机找个数,分比他的大,小的;分到单个数;在合并(merge函数是重点)
def merge_sort(alist):
"""
递归分治序列
:param alist:
:return:
"""
if len(alist) <= 1:
return alist
num = len(alist)//2
left = merge_sort(alist[:num])
right = merge_sort(alist[num:])
return merge(left, right) # 合并
def merge(left, right):
"""
合并操作
:param left:
:param right:
:return:
"""
l, r = 0, 0
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]: # 筛选排序将left与right最小元素按序加入新序列
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
-
拓扑 (图,之前存在依赖关系)
有向无环图,利用bfs|dfs进行处理,删除入度为0,查他周围,选择入度为0,处理。
image.png