Python，學霸
閱讀指南
原理
例項
輸出
gif演示制作
原理
選擇排序是一種簡單直觀的排序演算法。其原理是透過遍歷待排序的元素，每次選出最小（或最大）的元素，並將其放置在已排序序列的末尾。具體步驟如下：
首先，從待排序序列中找到最小（或最大）的元素，並將其與序列的第一個元素交換位置。
然後，在剩余的未排序序列中，繼續尋找最小（或最大）的元素，將其與序列的第二個元素交換位置。
以此類推，重復執行上述操作，直到所有元素都被排序。
例項
from typing import List
def selection_sort(arr: List[int]) -> List[int]:
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
#選擇排序演算法
arr = [9, 1, 7, 2, 5]
sorted_arr = selection_sort(arr)
print(sorted_arr) #輸出排序後的陣列
輸出
[1, 2, 5, 7, 9]
生成gif演示圖：
from PIL import Image, ImageDraw
import random
def generate_image(arr, moving_index, swap_index):
#圖片的基本參數
image_width = 800
image_height = 600
bar_width = 40
bar_padding = 10
x_offset = 50
#建立一個空白圖片
image = Image.new('RGB', (image_width, image_height), (255, 255, 255))
draw = ImageDraw.Draw(image)
#繪制柱狀圖
for i in range(len(arr)):
bar_height = arr[i] * (image_height - 100) // max(arr)
x0 = x_offset + i * (bar_width + bar_padding)
y0 = image_height - bar_height
x1 = x0 + bar_width
y1 = image_height
color = (255, 140, 0) # 未排序好的方塊顏色
if i in moving_index:
color = (0, 255, 0) # 正在移動的方塊顏色
elif i in swap_index:
color = (220, 20, 60) # 正在交換的方塊顏色
draw.rectangle([x0, y0, x1, y1], fill=color)
return image
def selection_sort_animation(arr):
frames = []
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
#生成移動過程幀
moving_index = [min_index]
frame = generate_image(arr, moving_index, [])
frames.append(frame)
#生成交換過程幀
swap_index = [i, min_index]
frame = generate_image(arr, [], swap_index)
frames.append(frame)
#交換元素
arr[i], arr[min_index] = arr[min_index], arr[i]
#生成當前最小值到正確位置的幀
frame = generate_image(arr, [], [])
frames.append(frame)
return frames
#選擇排序演算法
arr = [9, 1, 7, 2, 5] # 待排序數據
frames = selection_sort_animation(arr)
#保存為GIF
frames[0].save('sorting.gif', format='GIF',
append_images=frames[1:],
save_all=True,
duration=900,
loop=0)
相關文章：
