03排序
03排序
1. 插入排序
1.1 直接插入排序
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
- 时间复杂度为 。最好为顺序 ，最坏为逆序 。
- 稳定排序
- 空间复杂度为
1.2 希尔排序
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
- 平均时间复杂度约为 ，最差为退化为直接插入 。
- 不稳定排序
- 空间复杂度为
2. 交换排序
2.1 冒泡排序
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arr
优化版：
def bubble_sort(arr):
n = len(arr)
last_swap = n - 1
while last_swap > 0:
curr_swap = 0
for i in range(last_swap):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
curr_swap = i
last_swap = curr_swap
return arr
- 时间复杂度为 。最好为顺序 ，最坏为逆序 。
- 稳定排序
- 空间复杂度为
2.2 快速排序
简洁实现如下：
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
实际实现会原地进行 partition，避免额外空间开销：
def partition(arr, low: int, high: int) -> int:
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
再进行快排：
def quick_sort(arr, low, high):
if low >= high:
return
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
- 时间复杂度为 。最好为选取中位数 ，最坏为选取最大值或者最小值 。
- 不稳定排序
- 空间复杂度为
3. 选择排序
3.1 简单选择排序
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
- 时间复杂度为
- 不稳定排序
- 空间复杂度为
3.2 树形选择排序
类似于锦标赛
- 时间复杂度为
- 稳定排序
- 空间复杂度为
3.3 堆排序
首先递归构造堆：
def heapify(arr, n, i):
largest = i
if (left := get_left(i)) < n and arr[left] > arr[largest]:
largest = left
if (right := get_right(i)) < n and arr[right] > arr[largest]:
largest = right
if largest == i:
return
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
最后继续堆排序：
def heap_sort(arr):
n = len(arr)
for i in range(n//2-1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
- 时间复杂度为
- 不稳定排序
- 空间复杂度为
4. 归并排序
对于有序序列，可以直接合并：
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if (l := left[i]) <= (r := right[j]):
result.append(l)
i += 1
else:
result.append(r)
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
递归进行合并排序：
def merge_sort(arr):
if (n := len(arr)) < 2:
return arr
mid = n // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
- 时间复杂度为
- 稳定排序
- 空间复杂度为
