Python 中的選擇排序

Vaibhhav Khetarpal 2023年1月30日 2022年5月18日
  1. Python 中實現選擇排序的迭代方法
  2. Python 中實現選擇排序的遞迴方法
Python 中的選擇排序

本文討論了選擇排序演算法以及如何在 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
Vaibhhav Khetarpal avatar Vaibhhav Khetarpal avatar

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

相關文章 - Python Sort