关于python:Python选择排序简单而高效的排序算法解析

1次阅读

共计 2157 个字符，预计需要花费 6 分钟才能阅读完成。

抉择排序（Selection Sort）是一种简略但无效的排序算法。它的根本思维是每次从待排序的元素中抉择最小（或最大）的元素，并将其搁置在已排序序列的开端。通过屡次抉择和替换操作，逐渐将序列排序。本文将具体介绍抉择排序算法的原理和实现，并提供相干的 Python 代码示例。

抉择排序算法的步骤如下：

遍历待排序序列，将第一个元素视为以后最小（或最大）元素。
在残余的待排序序列中，找到最小（或最大）的元素，将其与以后地位替换。
排除已排序的元素，反复步骤 2，直到所有元素都被排序。

抉择排序的核心思想是通过屡次抉择最小（或最大）元素，逐渐将序列排序。

上面是应用 Python 实现抉择排序算法的代码：


def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        # 假如以后地位的元素为最小值
        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]

        # 测试代码
numbers = [4, 2, 6, 1, 3]
selection_sort(numbers)
print(numbers)  # 输入：[1, 2, 3, 4, 6]

在上述代码中，selection_sort() 函数承受一个待排序的列表作为输出，并对列表进行抉择排序。算法应用两个嵌套的循环。内部循环从第一个元素遍历到倒数第二个元素，外部循环从内部循环的下一个地位遍历到列表开端，寻找最小元素的索引。而后通过替换操作，将最小元素搁置在以后地位上。

抉择排序是一种旧址排序算法，即在排序过程中间接批改原始列表，不须要额定的存储空间。抉择排序的工夫复杂度为 O(n^2)，其中 n 是待排序序列的长度。尽管抉择排序的工夫复杂度较高，但在小规模数据或局部有序的数据集上，其性能依然能够承受。
抉择排序是一种不稳固的排序算法，即相等元素的绝对程序可能会产生扭转。例如，对于序列 [2, 2, 1]，通过抉择排序后，第一个 2 会被移到第二个 2 的前面。

只管抉择排序的工夫复杂度较高，但能够通过一些优化思路晋升算法性能。

在外部循环中，咱们每次找到最小元素后都会进行一次替换操作。实际上，咱们能够在外部循环完结后再进行一次替换操作，将最小元素搁置在正确的地位上。


def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        # 假如以后地位的元素为最小值
        min_index = i
        for j in range(i + 1, n):
            # 在残余局部中寻找最小值的索引
            if arr[j] < arr[min_index]:
                min_index = j
                # 将以后地位的元素与最小值进行替换
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]

这样能够缩小替换的次数，但并不会扭转算法的工夫复杂度。

在外部循环中，咱们每次都要查找残余局部中的最小元素的索引。能够应用双指针的形式，同时记录最小元素的索引和最大元素的索引，而后进行替换。


def selection_sort(arr):
    n = len(arr)
    left = 0
    right = n - 1
    while left < right:
        # 假如以后地位的元素为最小值和最大值
        min_index = left
        max_index = right
        for i in range(left, right + 1):
            # 在残余局部中寻找最小值和最大值的索引
            if arr[i] < arr[min_index]:
                min_index = i
            if arr[i] > arr[max_index]:
                max_index = i
                # 将以后地位的元素与最小值进行替换
        if min_index != left:
            arr[left], arr[min_index] = arr[min_index], arr[left]
        if max_index == left:
            max_index = min_index
            # 将以后地位的元素与最大值进行替换
        if max_index != right:
            arr[right], arr[max_index] = arr[max_index], arr[right]
        left += 1
        right -= 1

这种优化形式能够同时找到最小元素和最大元素的索引，并进行相应的替换操作。在一次循环中，咱们能够找到最小元素并将其搁置在正确的地位上，同时找到最大元素并将其搁置在正确的地位上。这样能够缩小比拟的次数。

抉择排序是一种简略但无效的排序算法。它的根本思维是每次抉择最小（或最大）的元素，并将其搁置在已排序序列的开端，通过屡次抉择和替换操作，逐渐将序列排序。本文介绍了抉择排序算法的原理和实现，并提供了相干的 Python 代码示例。抉择排序的工夫复杂度为 O(n^2)，在小规模数据或局部有序的数据集上，其性能能够承受。此外，咱们还介绍了一些优化思路，如缩小替换次数和应用双指针，以晋升算法的性能。把握抉择排序的实现和优化思路对于了解和利用其余排序算法也是很有帮忙的。
关注我，更多精彩内容立刻出现！

正文完