通过实现 6 种经典的排序算法,尽展 Python 的简而美~
def quick_sort(arr):
if len(arr) < 2:
return arr[:]
left = quick_sort([i for i in arr[1:] if i <= arr[0]])
right = quick_sort([i for i in arr[1:] if i > arr[0]])
return left + [arr[0]] + right
经典快排实现
def quick_sort(arr):
def partition(arr, s, e):
key = arr[0]
while s < e:
while s < e and arr[e] >= key: e -= 1
arr[s] = arr[e]
while s < e and arr[s] <= key: s += 1
arr[e] = arr[s]
return s
def quick_sort_recursion(arr, s, e):
if s < e:
idx = partition(arr, s, e)
quick_sort_recursion(arr, s, idx - 1)
quick_sort_recursion(arr, idx + 1, e)
quick_sort_recursion(arr, 0, len(arr) - 1)
return arr
def merge_sort(arr):
def merge(left, right):
rs = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
rs.append(left[i])
i += 1
else:
rs.append(right[j])
j += 1
rs += left[i:]
rs += right[j:]
return rs
def merge_sort_recursion(arr):
if len(arr) in [0, 1]: # 停止分裂,最小子问题
return arr
mid = len(arr) // 2
left = merge_sort_recursion(arr[:mid])
right = merge_sort_recursion(arr[mid:])
return merge(left, right)
return merge_sort_recursion(arr)
def heap_sort(arr):
def init_heap(arr):
n = len(arr)
last_parent = (n - 1) // 2 # 最后一个parent节点
for i in range(last_parent, -1, -1):
adjust_heap(arr, n, i)
def adjust_heap(arr, max_length, parent):
left = 2 * parent + 1
right = 2 * parent + 2
largest = parent
if left < max_length and arr[left] > arr[largest]:
largest = left
if right < max_length and arr[right] > arr[largest]:
largest = right
if parent != largest:
arr[parent], arr[largest] = arr[largest], arr[parent]
adjust_heap(arr, max_length, largest)
init_heap(arr) #初始化大顶堆
for i in range(len(arr) - 1, -1, -1):
arr[i], arr[0] = arr[0], arr[i] # 每次将最大值移到最后
adjust_heap(arr, i, 0)
return arr
def insert_sort(arr):
for i in range(1, len(arr)):
for j in range(i, 0, -1):
if arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
else:
break
return arr
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(0, n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j + 1], arr[j] = arr[j], arr[j + 1]
return arr
def select_sort(arr):
n = len(arr)
for i in range(0, n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[i]:
min_idx = j
if i != min_idx:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
if __name__ == '__main__':
import numpy as np
arr = list(np.random.randint(0, 100, 100))
print(quick_sort(arr))
print(merge_sort(arr))
print(heap_sort(arr))
print(bubble_sort(arr))
print(select_sort(arr))
print(insert_sort(arr))