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