Python 中的選擇排序
Vaibhhav Khetarpal
2023年1月30日
2022年5月18日
本文討論了選擇排序演算法以及如何在 Python 中實現它。
選擇排序是對小型資料結構進行排序的演算法之一。一個基本的基於比較的演算法可以將給定的陣列分成兩部分:排序
部分(左)和未排序
部分(右)。
該演算法旨在從未排序
部分中找到具有最小值的元素,並將其傳送到已排序
部分。重複此過程,直到給定陣列的未排序
部分不包含任何元素。
在選擇排序演算法的整個執行過程中,給定的陣列被分為兩個子陣列:
- 一個子陣列包含所有已排序的元素。
- 另一個子陣列包含所有尚未檢查的未排序元素。
有兩種實現選擇排序演算法的方法:迭代選擇排序
和遞迴選擇排序
。
Python 中實現選擇排序的迭代方法
可以使用簡單的迭代方法在 Python 中執行選擇排序。
此方法從未排序的子陣列中取出一個具有最小值的元素,並在 for
迴圈的每次迭代中將其放入已排序的子陣列中。
在 Python 中使用迭代方法實現選擇排序的示例程式碼。
def selectionSort(array, size):
for step in range(size):
min_a = step
for i in range(step + 1, size):
if array[i] < array[min_a]:
min_a = i
(array[step], array[min_a]) = (array[min_a], array[step])
X = [45, 22, 18, 32, 49]
size = len(X)
selectionSort(X, size)
print('Sorted Array is:')
print(X)
輸出:
Sorted Array is:
[18,22,32,45,49]
Python 中實現選擇排序的遞迴方法
遞迴過程是在 Python 中進行選擇排序的另一種方法。我們建立了一個函式,它在自身下遞迴呼叫未排序的部分。
使用遞迴方法在 Python 中實現選擇排序的示例程式碼。
def minIndex( a , x , y ):
if x == y:
return x
z = minIndex(a, x + 1, y)
return (x if a[x] < a[z] else z)
def RSS(a, n, index = 0):
if index == n:
return -1
z = minIndex(a, index, n-1)
if z != index:
a[z], a[index] = a[index], a[z]
RSS(a, n, index + 1)
l1 = [5, 7, 2, 4, 6]
n = len(l1)
RSS(l1, n)
for x in l1:
print(x, end = ' ')
輸出:
2 4 5 6 7
Author: Vaibhhav Khetarpal
Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.
LinkedIn