冒泡排序（Bubble Sort）¶
In [4]:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# 每一轮冒泡将最大的元素冒泡到末尾
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
bubble_sort([3, 1, 4, 5, 2])
# 时间复杂度：最好情况O(n)，平均和最坏情况O(n^2)
# 空间复杂度：O(1)
>>>>[ 3 1 4 5 2 ]
[0 ]-----------------
[0 ]=================
>>>>[(3){1} 4 5 2 ]
>>>>[(1){3} 4 5 2 ]
[1 ]=================
[2 ]=================
[3 ]=================
>>>>[ 1 3 4 (5){2}]
>>>>[ 1 3 4 (2){5}]
[1 ]-----------------
[0 ]=================
[1 ]=================
[2 ]=================
>>>>[ 1 3 (4){2} 5 ]
>>>>[ 1 3 (2){4} 5 ]
[2 ]-----------------
[0 ]=================
[1 ]=================
>>>>[ 1 (3){2} 4 5 ]
>>>>[ 1 (2){3} 4 5 ]
[3 ]-----------------
[0 ]=================
[4 ]-----------------
Out[4]:
[1, 2, 3, 4, 5]
插入排序（Insertion Sort）¶
In [10]:
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# 将比key大的元素向右移动一位
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
insertion_sort([3, 1, 4, 5, 2])
# 时间复杂度：最好情况O(n)，平均和最坏情况O(n^2)
# 空间复杂度：O(1)
>>>>[ 3 1 4 5 2 ]
[1 ]=================
>>>>[{3}(1) 4 5 2 ]
[0 ]-----------------
>>>>[(3){1} 4 5 2 ]
>>>>[(3) 3 4 5 2 ]
>>>>[(1) 3 4 5 2 ]
[2 ]=================
>>>>[ 1 {3}(4) 5 2 ]
>>>>[ 1 3 (4) 5 2 ]
>>>>[ 1 3 (4) 5 2 ]
[3 ]=================
>>>>[ 1 3 {4}(5) 2 ]
>>>>[ 1 3 4 (5) 2 ]
>>>>[ 1 3 4 (5) 2 ]
[4 ]=================
>>>>[ 1 3 4 {5}(2)]
[3 ]-----------------
>>>>[ 1 3 4 (5){2}]
[2 ]-----------------
>>>>[ 1 3 (4){5} 5 ]
[1 ]-----------------
>>>>[ 1 (3){4} 4 5 ]
>>>>[ 1 (3) 3 4 5 ]
>>>>[ 1 (2) 3 4 5 ]
Out[10]:
[1, 2, 3, 4, 5]
选择排序（Selection Sort）¶
时间复杂度：最好、最坏和平均情况下均为O(n^2)；空间复杂度：O(1)
In [12]:
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
selection_sort([3, 1, 4, 5, 2])
# 时间复杂度：最好情况、平均和最坏情况都是O(n^2)
# 空间复杂度：O(1)
>>>>[ 3 1 4 5 2 ]
[0 ]=================
[1 ]-----------------
>>>>[ 3 (1) 4 5 2 ]
[2 ]-----------------
[3 ]-----------------
[4 ]-----------------
>>>>[(3){1} 4 5 2 ]
>>>>[{1}(3) 4 5 2 ]
[1 ]=================
[2 ]-----------------
[3 ]-----------------
[4 ]-----------------
>>>>[ 1 3 4 5 (2)]
>>>>[ 1 (3) 4 5 {2}]
>>>>[ 1 {2} 4 5 (3)]
[2 ]=================
[3 ]-----------------
[4 ]-----------------
>>>>[ 1 2 4 5 (3)]
>>>>[ 1 2 (4) 5 {3}]
>>>>[ 1 2 {3} 5 (4)]
[3 ]=================
[4 ]-----------------
>>>>[ 1 2 3 5 (4)]
>>>>[ 1 2 3 (5){4}]
>>>>[ 1 2 3 {4}(5)]
[4 ]=================
>>>>[ 1 2 3 4 (5)]
>>>>[ 1 2 3 4 (5)]
Out[12]:
[1, 2, 3, 4, 5]
快速排序（QuickSort）¶
时间复杂度：最好和平均情况O(nlogn)，最坏情况O(n^2) 空间复杂度：最好和平均情况O(logn)，最坏情况O(n)
In [16]:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
arr = [3, 1, 4, 5, 2, 1]
print(quicksort(arr))
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
lesser = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(lesser) + [pivot] + quick_sort(greater)
print(quick_sort(arr))
===================== 555555555555555555555 >>>>[ 3 1 4 2 1 ] >>>>[ 5 ] >>>>[] ===================== 444444444444444444444 >>>>[ 3 1 2 1 ] >>>>[ 4 ] >>>>[] ===================== 222222222222222222222 >>>>[ 1 1 ] >>>>[ 2 ] >>>>[ 3 ] ===================== 111111111111111111111 >>>>[] >>>>[ 1 1 ] >>>>[] [1, 1, 2, 3, 4, 5] ********************* 333333333333333333333 >>>>[ 1 2 1 ] >>>>[ 4 5 ] 111111111111111111111 >>>>[ 1 ] >>>>[ 2 ] 444444444444444444444 >>>>[] >>>>[ 5 ] [1, 1, 2, 3, 4, 5]
归并排序（MergeSort）¶
这段代码实现了归并排序算法。首先，merge_sort函数用递归的方式将数组不断二分，直到数组长度为1或者更小。然后，调用merge函数将左右两个已排序的子数组合并成一个有序的数组。最后，使用merge_sort函数对整个数组进行排序 时间复杂度：最好、平均和最坏情况都是O(nlogn) 空间复杂度：O(n)
In [20]:
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)
def merge(left, right):
merged = []
left_index, right_index = 0, 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
while left_index < len(left):
merged.append(left[left_index])
left_index += 1
while right_index < len(right):
merged.append(right[right_index])
right_index += 1
return merged
# 测试示例
arr = [3, 1, 4, 5, 2, 1]
sorted_arr = merge_sort(arr)
print(sorted_arr)
333333333333333333333 >>>>[ 3 1 4 ] 111111111111111111111 >>>>[ 3 ] >>>>[ 3 ] ********************* >>>>[ 1 4 ] 111111111111111111111 >>>>[ 1 ] >>>>[ 1 ] ********************* >>>>[ 4 ] >>>>[ 4 ] >>>>[ 1 4 ] >>>>[ 1 3 4 ] ********************* >>>>[ 5 2 1 ] 111111111111111111111 >>>>[ 5 ] >>>>[ 5 ] ********************* >>>>[ 2 1 ] 111111111111111111111 >>>>[ 2 ] >>>>[ 2 ] ********************* >>>>[ 1 ] >>>>[ 1 ] >>>>[ 1 2 ] >>>>[ 1 2 5 ] [1, 1, 2, 3, 4, 5]
堆排序（HeapSort）¶
上述代码实现了堆排序算法。首先，heapify函数用于将给定的数组调整为最大堆，即每个父节点都大于或等于其子节点。它接收三个参数：数组、数组长度和当前节点索引。在函数中，首先假设当前节点是最大值，并检查其左右子节点是否比它大，如果是，则更新最大值的索引。然后，如果最大值不是父节点，则进行交换，并递归调整子树。这样就可以保证每个子树都是最大堆。 接下来，heap_sort函数用于对整个数组进行排序。首先，通过循环从最后一个非叶子节点开始，逐个调用heapify函数构建最大堆。然后，再次通过循环，从堆中取出根节点（当前最大值）并将其移到数组末尾，然后再次调用heapify函数调整堆。重复这个过程直到整个数组有序。
In [28]:
def heapify(arr, n, i):
largest = i # 假设当前节点是最大值
left = 2 * i + 1 # 左子节点的索引
right = 2 * i + 2 # 右子节点的索引
# 检查左子节点是否大于父节点
if left < n and arr[left] > arr[largest]:
largest = left
# 检查右子节点是否大于父节点
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大值不是父节点，则进行交换，并递归调整子树
if largest != i:
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[i], arr[0] = arr[0], arr[i] # 将当前最大值移到末尾
heapify(arr, i, 0) # 调整堆
return arr
# 测试示例
arr = [9, 5, 7, 1, 3, 8, 2, 6, 4]
sorted_arr = heap_sort(arr)
print(sorted_arr)
[3 ]=================
[3 ]-----------------
>>>>[ 9 5 7 (1) 3 8 2 6 4 ]
>>>>[ 9 5 7 1 3 8 2 (6) 4 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[ 9 5 7 (1) 3 8 2 {6} 4 ]
>>>>[ 9 5 7 {6} 3 8 2 (1) 4 ]
[7 ]-----------------
>>>>[ 9 5 7 6 3 8 2 (1) 4 ]
>>>>[ 9 5 7 6 3 8 2 (1) 4 ]
[2 ]=================
[2 ]-----------------
>>>>[ 9 5 (7) 6 3 8 2 1 4 ]
>>>>[ 9 5 7 6 3 (8) 2 1 4 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[ 9 5 (7) 6 3 {8} 2 1 4 ]
>>>>[ 9 5 {8} 6 3 (7) 2 1 4 ]
[5 ]-----------------
>>>>[ 9 5 8 6 3 (7) 2 1 4 ]
>>>>[ 9 5 8 6 3 (7) 2 1 4 ]
[1 ]=================
[1 ]-----------------
>>>>[ 9 (5) 8 6 3 7 2 1 4 ]
>>>>[ 9 5 8 (6) 3 7 2 1 4 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[ 9 (5) 8 {6} 3 7 2 1 4 ]
>>>>[ 9 {6} 8 (5) 3 7 2 1 4 ]
[3 ]-----------------
>>>>[ 9 6 8 (5) 3 7 2 1 4 ]
>>>>[ 9 6 8 (5) 3 7 2 1 4 ]
[0 ]=================
[0 ]-----------------
>>>>[(9) 6 8 5 3 7 2 1 4 ]
>>>>[(9) 6 8 5 3 7 2 1 4 ]
*********************
[8 ]=================
>>>>[(9) 6 8 5 3 7 2 1 {4}]
>>>>[{4} 6 8 5 3 7 2 1 (9)]
[0 ]-----------------
>>>>[(4) 6 8 5 3 7 2 1 9 ]
>>>>[ 4 6 (8) 5 3 7 2 1 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[(4) 6 {8} 5 3 7 2 1 9 ]
>>>>[{8} 6 (4) 5 3 7 2 1 9 ]
[2 ]-----------------
>>>>[ 8 6 (4) 5 3 7 2 1 9 ]
>>>>[ 8 6 4 5 3 (7) 2 1 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[ 8 6 (4) 5 3 {7} 2 1 9 ]
>>>>[ 8 6 {7} 5 3 (4) 2 1 9 ]
[5 ]-----------------
>>>>[ 8 6 7 5 3 (4) 2 1 9 ]
>>>>[ 8 6 7 5 3 (4) 2 1 9 ]
[7 ]=================
>>>>[(8) 6 7 5 3 4 2 {1} 9 ]
>>>>[{1} 6 7 5 3 4 2 (8) 9 ]
[0 ]-----------------
>>>>[(1) 6 7 5 3 4 2 8 9 ]
>>>>[ 1 6 (7) 5 3 4 2 8 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[(1) 6 {7} 5 3 4 2 8 9 ]
>>>>[{7} 6 (1) 5 3 4 2 8 9 ]
[2 ]-----------------
>>>>[ 7 6 (1) 5 3 4 2 8 9 ]
>>>>[ 7 6 1 5 3 (4) 2 8 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[ 7 6 (1) 5 3 {4} 2 8 9 ]
>>>>[ 7 6 {4} 5 3 (1) 2 8 9 ]
[5 ]-----------------
>>>>[ 7 6 4 5 3 (1) 2 8 9 ]
>>>>[ 7 6 4 5 3 (1) 2 8 9 ]
[6 ]=================
>>>>[(7) 6 4 5 3 1 {2} 8 9 ]
>>>>[{2} 6 4 5 3 1 (7) 8 9 ]
[0 ]-----------------
>>>>[(2) 6 4 5 3 1 7 8 9 ]
>>>>[ 2 (6) 4 5 3 1 7 8 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[(2){6} 4 5 3 1 7 8 9 ]
>>>>[{6}(2) 4 5 3 1 7 8 9 ]
[1 ]-----------------
>>>>[ 6 (2) 4 5 3 1 7 8 9 ]
>>>>[ 6 2 4 (5) 3 1 7 8 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[ 6 (2) 4 {5} 3 1 7 8 9 ]
>>>>[ 6 {5} 4 (2) 3 1 7 8 9 ]
[3 ]-----------------
>>>>[ 6 5 4 (2) 3 1 7 8 9 ]
>>>>[ 6 5 4 (2) 3 1 7 8 9 ]
[5 ]=================
>>>>[(6) 5 4 2 3 {1} 7 8 9 ]
>>>>[{1} 5 4 2 3 (6) 7 8 9 ]
[0 ]-----------------
>>>>[(1) 5 4 2 3 6 7 8 9 ]
>>>>[ 1 (5) 4 2 3 6 7 8 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[(1){5} 4 2 3 6 7 8 9 ]
>>>>[{5}(1) 4 2 3 6 7 8 9 ]
[1 ]-----------------
>>>>[ 5 (1) 4 2 3 6 7 8 9 ]
>>>>[ 5 1 4 2 (3) 6 7 8 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[ 5 (1) 4 2 {3} 6 7 8 9 ]
>>>>[ 5 {3} 4 2 (1) 6 7 8 9 ]
[4 ]-----------------
>>>>[ 5 3 4 2 (1) 6 7 8 9 ]
>>>>[ 5 3 4 2 (1) 6 7 8 9 ]
[4 ]=================
>>>>[(5) 3 4 2 {1} 6 7 8 9 ]
>>>>[{1} 3 4 2 (5) 6 7 8 9 ]
[0 ]-----------------
>>>>[(1) 3 4 2 5 6 7 8 9 ]
>>>>[ 1 3 (4) 2 5 6 7 8 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[(1) 3 {4} 2 5 6 7 8 9 ]
>>>>[{4} 3 (1) 2 5 6 7 8 9 ]
[2 ]-----------------
>>>>[ 4 3 (1) 2 5 6 7 8 9 ]
>>>>[ 4 3 (1) 2 5 6 7 8 9 ]
[3 ]=================
>>>>[(4) 3 1 {2} 5 6 7 8 9 ]
>>>>[{2} 3 1 (4) 5 6 7 8 9 ]
[0 ]-----------------
>>>>[(2) 3 1 4 5 6 7 8 9 ]
>>>>[ 2 (3) 1 4 5 6 7 8 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[(2){3} 1 4 5 6 7 8 9 ]
>>>>[{3}(2) 1 4 5 6 7 8 9 ]
[1 ]-----------------
>>>>[ 3 (2) 1 4 5 6 7 8 9 ]
>>>>[ 3 (2) 1 4 5 6 7 8 9 ]
[2 ]=================
>>>>[(3) 2 {1} 4 5 6 7 8 9 ]
>>>>[{1} 2 (3) 4 5 6 7 8 9 ]
[0 ]-----------------
>>>>[(1) 2 3 4 5 6 7 8 9 ]
>>>>[ 1 (2) 3 4 5 6 7 8 9 ]
~~~~~~~~~~~~~~~~~~~~~
>>>>[(1){2} 3 4 5 6 7 8 9 ]
>>>>[{2}(1) 3 4 5 6 7 8 9 ]
[1 ]-----------------
>>>>[ 2 (1) 3 4 5 6 7 8 9 ]
>>>>[ 2 (1) 3 4 5 6 7 8 9 ]
[1 ]=================
>>>>[(2){1} 3 4 5 6 7 8 9 ]
>>>>[{1}(2) 3 4 5 6 7 8 9 ]
[0 ]-----------------
>>>>[(1) 2 3 4 5 6 7 8 9 ]
>>>>[(1) 2 3 4 5 6 7 8 9 ]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
基数排序（Radix Sort）¶
是一种非比较排序算法，它的基本思想是将待排序的数据按照位数分组，然后对每一组进行排序，最终得到有序的结果。
In [45]:
def radix_sort(lst):
# 找到最长的数字长度
max_len = max(len(x) for x in lst)
print("找到最大值，确定排序位数", max_len)
# 从个位开始，逐位进行排序
for i in range(max_len):
print(f"对第{i+1}位进行排序")
# 将数据按照当前位数分组，考虑数字长度不足的情况
groups = [[] for _ in range(10)]
for num in lst:
# 处理位数不足的情况，短的数字在高位视为0
if len(num) - i - 1 >= 0:
digit = num[-(i + 1)]
else:
digit = '0'
print("当前数", num, "当前位", digit)
groups[int(digit)].append(num)
print(groups)
# 重新组合列表
lst = [num for group in groups for num in group]
return lst
lst = ['13', '431','6', '723', '555', '281']
sorted_lst = radix_sort(lst)
print(sorted_lst)
找到最大值，确定排序位数 3 对第1位进行排序 当前数 13 当前位 3 [[], [], [], ['13'], [], [], [], [], [], []] 当前数 431 当前位 1 [[], ['431'], [], ['13'], [], [], [], [], [], []] 当前数 6 当前位 6 [[], ['431'], [], ['13'], [], [], ['6'], [], [], []] 当前数 723 当前位 3 [[], ['431'], [], ['13', '723'], [], [], ['6'], [], [], []] 当前数 555 当前位 5 [[], ['431'], [], ['13', '723'], [], ['555'], ['6'], [], [], []] 当前数 281 当前位 1 [[], ['431', '281'], [], ['13', '723'], [], ['555'], ['6'], [], [], []] 对第2位进行排序 当前数 431 当前位 3 [[], [], [], ['431'], [], [], [], [], [], []] 当前数 281 当前位 8 [[], [], [], ['431'], [], [], [], [], ['281'], []] 当前数 13 当前位 1 [[], ['13'], [], ['431'], [], [], [], [], ['281'], []] 当前数 723 当前位 2 [[], ['13'], ['723'], ['431'], [], [], [], [], ['281'], []] 当前数 555 当前位 5 [[], ['13'], ['723'], ['431'], [], ['555'], [], [], ['281'], []] 当前数 6 当前位 0 [['6'], ['13'], ['723'], ['431'], [], ['555'], [], [], ['281'], []] 对第3位进行排序 当前数 6 当前位 0 [['6'], [], [], [], [], [], [], [], [], []] 当前数 13 当前位 0 [['6', '13'], [], [], [], [], [], [], [], [], []] 当前数 723 当前位 7 [['6', '13'], [], [], [], [], [], [], ['723'], [], []] 当前数 431 当前位 4 [['6', '13'], [], [], [], ['431'], [], [], ['723'], [], []] 当前数 555 当前位 5 [['6', '13'], [], [], [], ['431'], ['555'], [], ['723'], [], []] 当前数 281 当前位 2 [['6', '13'], [], ['281'], [], ['431'], ['555'], [], ['723'], [], []] ['6', '13', '281', '431', '555', '723']
In [ ]: