学个排序~
前言
该补充的算法基础还是要补TuT
快排（Quick Sort）
思路总结:
以某个位置为轴，大于轴的数都移动至右侧，小于轴的数都移动到左侧，轴左右侧的新列表递归选取轴和按大小排列
复杂度：
平均：O(nlogn)； 最差：O(n^2)
代码：
def quick_sort(A):
quick_sort2(A, 0, len(A)-1)
def quick_sort2(A, low, hi):
# 递归方法
if hi > low:
p = partition(A, low, hi)
quick_sort2(A, low, p-1)
quick_sort2(A, p+1, hi)
def partition(A, low, hi):
# 获取轴
# [轴, 小于轴, 小于轴, 小于轴, 大于轴, 大于轴, 大于轴, 大于轴]
# [小于轴, 小于轴, 小于轴, 轴, 大于轴, 大于轴, 大于轴, 大于轴]
# 返回轴
privot = get_privot(A, low, hi)
privot_value = A[privot]
A[low], A[privot] = privot_value, A[low]
border = low
for i in range(low+1, hi+1):
if A[i] < privot_value:
border += 1
A[i], A[border] = A[border], A[i]
A[low], A[border] = A[border], A[low]
return border
def get_privot(A, low, hi):
# 选取一个位置为轴
# 若不选取中间值为轴 最差O(n^2)
mid = (hi + low) // 2
s = sorted([A[hi], A[low], A[mid]])
if s[1] == A[hi]:
return hi
elif s[1] == A[low]:
return low
else:
return mid
插入排序（Insertion Sort）
思路：
从左往右，拿起一个数，向左侧找它应该插入的位置
复杂度：
O(n^2)
代码：
def insert_sort(A):
n = len(A)
for i in range(1, n):
# 拿起一个元素
cur_val = A[i]
k = 0
# 比它大的都往右挪一格
for j in range(i-1, -2, -1):
k = j
if cur_val < A[j]:
A[j+1] = A[j]
else:
break
# 挪出来空的一格把该元素放入
A[k+1] = cur_val
选择排序（Selection Sort）
思路：
从左往右，找最小值放到最左边
复杂度：
O(n^2)
代码：
def select_sort(A):
n = len(A)
for i in range(0, n):
# 找出A[i:end]中的最小值
min_idx = i
for j in range(i+1, n):
if A[j] < A[min_idx]:
min_idx = j
# 将这个最小值交换值A[i]的位置
if min_idx != i:
A[min_idx], A[i] = A[i], A[min_idx]
冒泡排序（Bubble Sort）
思路：
从左往右，左侧比右侧大，则交换；一直交换至最右侧，依次排出：第n位为0至n的最大值，第n-1位为0至n-1的最大值
复杂度：
O(n^2)
代码：
def bubble_sort(A):
n = len(A)
for i in range(n):
for j in range(0, n-i-1):
if A[j] > A[j+1]:
A[j], A[j+1] = A[j+1], A[j]
归并排序（Merge Sort）
思路：
将列表分为两份，分别对左侧和右侧进行归并排序，排序完之后比较左侧和右侧第一个的大小，小的先放进结果中，再取下一个较小的放入结果，直至取完所有结果
复杂度：
O(nlogn)
代码：
def merge_sort(A):
merge_sort2(A, 0, len(A)-1)
def merge_sort2(A, first, last):
if last > first:
# 拆分为左右两组 分别归并排序
mid = (first+last) // 2
merge_sort2(A, first, mid)
merge_sort2(A, mid+1, last)
# 合并左右结果
merge(A, first, mid, last)
def merge(A, first, mid, last):
left = A[first:mid+1]
right = A[mid+1:last+1]
left.append(9999999999)
right.append(9999999999)
i = j = 0
# 依次取左右较小的作为第A[k]值，直至拼接成完整的A[first:last+1]
for k in range(first, last+1):
if left[i] <= right[j]:
A[k] = left[i]
i += 1
else:
A[k] = right[j]
j += 1