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