【可视化探索】七种经典排序算法及其Python实现
冒泡排序算法
冒泡排序是一种简单的排序算法，它通过反复交换相邻的元素将最大的元素逐渐“冒泡”到数组的末尾。代码示例中的冒泡排序算法通过比较相邻元素并交换它们的位置来实现排序。动画演示了排序过程，每次比较都会将当前比较的两个元素标记为红色。
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import time
# 修改后的冒泡排序算法
def bubble_sort(arr):
n = len(arr)
steps = []
for i in range(n):
for j in range(0, n - i - 1):
# 先给颜色再交换位置
if arr[j] > arr[j + 1]:
steps.append((arr.copy(), j, j + 1)) # 记录排序过程和当前比较的位置
arr[j], arr[j + 1] = arr[j + 1], arr[j]
steps.append((arr.copy(), j, j + 1)) # 记录排序过程和当前比较的位置
else:
steps.append((arr.copy(), j, j + 1)) # 记录排序过程和当前比较的位置
return steps
# 随机生成一个数组
arr = np.random.randint(0, 100, 20)
# 获取排序步骤
steps = bubble_sort(arr.copy())
# 创建动画
fig, ax = plt.subplots()
ax.set_xlim(-1, len(arr))
ax.set_ylim(0, max(arr) + 10)
bar_rects = ax.bar(range(len(arr)), arr, align="edge")
def animate(i):
current_step = steps[i][0]
compare_idx1 = steps[i][1]
compare_idx2 = steps[i][2]
for idx, (rect, val) in enumerate(zip(bar_rects, current_step)):
if idx == compare_idx1 or idx == compare_idx2:
rect.set_color('r') # 将比较的柱子设为红色
else:
rect.set_color('b') # 其余柱子设为蓝色
rect.set_height(val)
time.sleep(0.5)
return bar_rects
ani = animation.FuncAnimation(fig, animate, frames=len(steps), interval=50, blit=True)
plt.show()堆排序
堆排序是一种基于二叉堆的排序算法，它利用了堆的性质来实现排序。堆排序的主要思想是将待排序的序列构建成一个大顶堆，然后依次将堆顶元素与末尾元素交换，再调整堆，直到整个序列有序为止。
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import time
# 修改后的堆排序算法
def heapify(arr, n, i, steps):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
steps.append((arr.copy(), i, largest))
arr[i], arr[largest] = arr[largest], arr[i]
steps.append((arr.copy(), i, largest)) # 记录排序过程
heapify(arr, n, largest, steps)
def heap_sort(arr):
n = len(arr)
steps = []
# Build a maxheap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i, steps)
# One by one extract elements
for i in range(n - 1, 0, -1):
steps.append((arr.copy(), 0, i))
arr[i], arr[0] = arr[0], arr[i]
steps.append((arr.copy(), 0, i)) # 记录排序过程
heapify(arr, i, 0, steps)
return steps
# 随机生成一个数组
arr = np.random.randint(0, 100, 20)
# 获取排序步骤
steps = heap_sort(arr.copy())
# 创建动画
fig, ax = plt.subplots()
ax.set_xlim(-1, len(arr))
ax.set_ylim(0, max(arr) + 10)
bar_rects = ax.bar(range(len(arr)), arr, align="edge")
def animate(i):
current_step = steps[i][0]
swap_idx1 = steps[i][1]
swap_idx2 = steps[i][2]
for idx, (rect, val) in enumerate(zip(bar_rects, current_step)):
if idx == swap_idx1 or idx == swap_idx2:
rect.set_color('r') # 将交换的柱子设为红色
else:
rect.set_color('b') # 其余柱子设为蓝色
rect.set_height(val)
time.sleep(0.5) # 可以适当调整延迟以观察排序过程
return bar_rects
ani = animation.FuncAnimation(fig, animate, frames=len(steps), interval=50, blit=True)
plt.show()
希尔排序算法
希尔排序是一种改进的插入排序算法，它通过将原始序列分割成若干子序列来提高插入排序的效率。希尔排序的关键在于选择合适的间隔序列，以便在每一轮排序中减少元素之间的距离，从而加快排序速度。
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import time
# 修改后的希尔排序算法
def shell_sort(arr):
n = len(arr)
steps = []
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:
steps.append((arr.copy(), j, j - gap)) # 记录排序过程和当前比较的位置
arr[j] = arr[j - gap]
j -= gap
steps.append((arr.copy(), j, j - gap)) # 记录排序过程和当前比较的位置
steps.append((arr.copy(), j, j))
arr[j] = temp
steps.append((arr.copy(), j, j)) # 记录排序过程和当前比较的位置
gap //= 2 # 缩小间隔
return steps
# 随机生成一个数组
arr = np.random.randint(0, 100, 20)
# 获取排序步骤
steps = shell_sort(arr.copy())
# 创建动画
fig, ax = plt.subplots()
ax.set_xlim(-1, len(arr))
ax.set_ylim(0, max(arr) + 10)
bar_rects = ax.bar(range(len(arr)), arr, align="edge")
def animate(i):
current_step = steps[i][0]
compare_idx1 = steps[i][1]
compare_idx2 = steps[i][2]
for idx, (rect, val) in enumerate(zip(bar_rects, current_step)):
if idx == compare_idx1 or idx == compare_idx2:
rect.set_color('r') # 将比较的柱子设为红色
time.sleep(0.5)
else:
rect.set_color('b') # 其余柱子设为蓝色
rect.set_height(val)
time.sleep(0.05) # 可以适当调整延迟以观察排序过程
return bar_rects
ani = animation.FuncAnimation(fig, animate, frames=len(steps), interval=50, blit=True)
plt.show()
归并排序
归并排序是一种分治算法，它将原始序列分成两个子序列，分别对子序列进行排序，然后将排好序的子序列合并成一个有序序列。归并排序的关键在于合并操作，它通过比较两个子序列的元素来将它们合并成一个有序序列。
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import time
# 修改后的归并排序算法
def merge_sort(arr):
def merge(left, right, steps):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged.append(left[i])
i += 1
steps.append((merged.copy(), i - 1, -1)) # 记录排序过程
else:
merged.append(right[j])
j += 1
steps.append((merged.copy(), -1, j - 1)) # 记录排序过程
# Append any remaining elements
while i < len(left):
merged.append(left[i])
i += 1
steps.append((merged.copy(), i - 1, -1)) # 记录排序过程
while j < len(right):
merged.append(right[j])
j += 1
steps.append((merged.copy(), -1, j - 1)) # 记录排序过程
return merged, steps
def merge_sort_helper(arr, steps):
if len(arr) <= 1:
return arr, steps
mid = len(arr) // 2
left, steps = merge_sort_helper(arr[:mid], steps)
right, steps = merge_sort_helper(arr[mid:], steps)
merged, steps = merge(left, right, steps)
return merged, steps
steps = []
sorted_arr, steps = merge_sort_helper(arr, steps)
return steps
# 随机生成一个数组
arr = np.random.randint(0, 100, 20)
# 获取排序步骤
steps = merge_sort(arr.copy())
# 创建动画
fig, ax = plt.subplots()
ax.set_xlim(-1, len(arr))
ax.set_ylim(0, max(arr) + 10)
bar_rects = ax.bar(range(len(arr)), arr, align="edge")
def animate(i):
current_step = steps[i][0]
highlight_left = steps[i][1]
highlight_right = steps[i][2]
for idx, (rect, val) in enumerate(zip(bar_rects, current_step)):
if idx == highlight_left:
rect.set_color('r') # 将左侧合并的柱子设为红色
elif idx == highlight_right:
rect.set_color('g') # 将右侧合并的柱子设为绿色
else:
rect.set_color('b') # 其余柱子设为蓝色
rect.set_height(val)
time.sleep(0.05) # 可以适当调整延迟以观察排序过程
return bar_rects
ani = animation.FuncAnimation(fig, animate, frames=len(steps), interval=50, blit=True)
plt.show()
快速排序算法
快速排序是一种高效的排序算法，它通过选择一个基准元素将原始序列分成两个子序列，然后递归地对子序列进行排序。快速排序的关键在于选择合适的基准元素和划分子序列的方法，以确保排序的效率和稳定性。
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import time
# 快速排序算法
def quick_sort(arr, low, high, steps):
if low < high:
pi = partition(arr, low, high, steps)
quick_sort(arr, low, pi - 1, steps)
quick_sort(arr, pi + 1, high, steps)
def partition(arr, low, high, steps):
pivot = arr[high]
i = low - 1
for j in range(low, high):
steps.append((arr.copy(), j, high)) # 记录当前比较的位置
if arr[j] < pivot:
# steps.append((arr.copy(), i, j))
i += 1
arr[i], arr[j] = arr[j], arr[i]
steps.append((arr.copy(), i, j)) # 记录交换后的位置
steps.append((arr.copy(), i + 1, high))
arr[i + 1], arr[high] = arr[high], arr[i + 1]
steps.append((arr.copy(), i + 1, high)) # 记录交换后的位置
return i + 1
# 随机生成一个数组
arr = np.random.randint(0, 100, 20)
steps = []
# 获取排序步骤
quick_sort(arr.copy(), 0, len(arr) - 1, steps)
# 创建动画
fig, ax = plt.subplots()
ax.set_xlim(-1, len(arr))
ax.set_ylim(0, max(arr) + 10)
bar_rects = ax.bar(range(len(arr)), arr, align="edge")
def animate(i):
current_step = steps[i][0]
compare_idx1 = steps[i][1]
compare_idx2 = steps[i][2]
for idx, (rect, val) in enumerate(zip(bar_rects, current_step)):
if idx == compare_idx1 or idx == compare_idx2:
time.sleep(0.5)
rect.set_color('r') # 将比较的柱子设为红色
else:
rect.set_color('b') # 其余柱子设为蓝色
rect.set_height(val)
return bar_rects
ani = animation.FuncAnimation(fig, animate, frames=len(steps), interval=50, blit=True)
plt.show()
插入排序算法
插入排序是一种简单直观的排序算法，它通过构建有序序列，对未排序的数据逐个插入到已排序序列中的适当位置。插入排序的关键在于比较和移动元素的过程，它通过不断地将当前元素与已排序序列的元素比较并移动来实现排序。
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import time
# 插入排序算法
def insertion_sort(arr):
n = len(arr)
steps = []
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
steps.append((arr.copy(), j, j + 1))
arr[j + 1] = arr[j]
steps.append((arr.copy(), j, j + 1)) # 记录排序过程和当前比较的位置
j -= 1
steps.append((arr.copy(), j + 1, j + 1))
arr[j + 1] = key
steps.append((arr.copy(), j + 1, j + 1)) # 记录排序过程和当前比较的位置
return steps
# 随机生成一个数组
arr = np.random.randint(0, 100, 20)
# 获取排序步骤
steps = insertion_sort(arr.copy())
# 创建动画
fig, ax = plt.subplots()
ax.set_xlim(-1, len(arr))
ax.set_ylim(0, max(arr) + 10)
bar_rects = ax.bar(range(len(arr)), arr, align="edge")
def animate(i):
current_step = steps[i][0]
compare_idx1 = steps[i][1]
compare_idx2 = steps[i][2]
for idx, (rect, val) in enumerate(zip(bar_rects, current_step)):
if idx == compare_idx1 or idx == compare_idx2:
time.sleep(0.5)
rect.set_color('r') # 将比较的柱子设为红色
else:
rect.set_color('b') # 其余柱子设为蓝色
rect.set_height(val)
return bar_rects
ani = animation.FuncAnimation(fig, animate, frames=len(steps), interval=50, blit=True)
plt.show()
计数排序算法
计数排序是一种非比较排序算法，它通过统计每个元素在序列中出现的次数来实现排序。计数排序的关键在于统计元素出现次数并将其存储在辅助数组中，然后根据统计信息将元素按照顺序放回原始序列中。
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import time
# 修改后的计数排序算法
def counting_sort(arr):
n = len(arr)
steps = []
# 找到数组中的最大值和最小值
max_val = max(arr)
min_val = min(arr)
# 初始化计数数组
count = [0] * (max_val - min_val + 1)
# 计数每个元素的频率
for i in range(n):
count[arr[i] - min_val] += 1
steps.append((arr.copy(), i, arr[i])) # 记录排序过程和当前处理的元素
# 重建排序数组
index = 0
for i in range(len(count)):
while count[i] > 0:
arr[index] = i + min_val
count[i] -= 1
index += 1
steps.append((arr.copy(), index - 1, i + min_val)) # 记录排序过程
return steps
# 随机生成一个数组
arr = np.random.randint(0, 100, 20)
# 获取排序步骤
steps = counting_sort(arr.copy())
# 创建动画
fig, ax = plt.subplots()
ax.set_xlim(-1, len(arr))
ax.set_ylim(0, max(arr) + 10)
bar_rects = ax.bar(range(len(arr)), arr, align="edge")
def animate(i):
current_step = steps[i][0]
highlight_idx = steps[i][1]
highlight_val = steps[i][2]
for idx, (rect, val) in enumerate(zip(bar_rects, current_step)):
if idx == highlight_idx:
rect.set_color('r') # 将处理的柱子设为红色
else:
rect.set_color('b') # 其余柱子设为蓝色
rect.set_height(val)
time.sleep(0.05) # 可以适当调整延迟以观察排序过程
return bar_rects
ani = animation.FuncAnimation(fig, animate, frames=len(steps), interval=50, blit=True)
plt.show()
选择排序算法
选择排序是一种简单直观的排序算法，它通过不断地选择最小（或最大）的元素放到已排序序列的末尾来实现排序。选择排序的关键在于选择最小（或最大）元素的过程，它通过遍历未排序的数据并找到最小（或最大）的元素来实现排序。
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import time
# 选择排序算法
def selection_sort(arr):
n = len(arr)
steps = []
for i in range(n):
min_idx = i
for j in range(i + 1, n):
# 记录当前比较的位置
steps.append((arr.copy(), min_idx, j))
if arr[j] < arr[min_idx]:
min_idx = j
steps.append((arr.copy(), i, min_idx))
# 交换位置
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# 记录交换后的位置
steps.append((arr.copy(), i, min_idx))
return steps
# 随机生成一个数组
arr = np.random.randint(0, 100, 20)
# 获取排序步骤
steps = selection_sort(arr.copy())
# 创建动画
fig, ax = plt.subplots()
ax.set_xlim(-1, len(arr))
ax.set_ylim(0, max(arr) + 10)
bar_rects = ax.bar(range(len(arr)), arr, align="edge")
def animate(i):
current_step = steps[i][0]
compare_idx1 = steps[i][1]
compare_idx2 = steps[i][2]
for idx, (rect, val) in enumerate(zip(bar_rects, current_step)):
if idx == compare_idx1 or idx == compare_idx2:
rect.set_color('r') # 将比较的柱子设为红色
# time.sleep(0.5)
else:
rect.set_color('b') # 其余柱子设为蓝色
rect.set_height(val)
time.sleep(0.5)
return bar_rects
ani = animation.FuncAnimation(fig, animate, frames=len(steps), interval=50, blit=True)
plt.show()
注意事项：运行时在本地终端中运行，否则效果不理想。
最终效果
通过学习和理解这些常见的排序算法，我们可以更好地应用它们解决实际问题，并提高程序的性能和效率。希望本文能够帮助读者深入了解排序算法的原理和实现方式，进而在实际工作中应用它们解决各种排序问题。
原文始发于微信公众号（索隆程序员）：【可视化探索】七种经典排序算法及其Python实现
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/244389.html
