选择排序算法

什么是选择排序？

选择排序算法将数组分为两部分：已排序部分和未排序部分。最初，已排序部分为空，未排序部分包含所有元素。该算法的工作原理是从未排序部分中找到最小（或最大，取决于排序顺序）元素，并将其与未排序部分的第一个元素交换。这个过程一直持续到整个数组被排序为止。

算法步骤

1. 从数组中的第一个元素开始，并假设它是最小的。
2. 将此元素与数组中的其他元素进行比较。
3. 如果找到较小的元素，请将其与第一个元素交换。
4. 移动到数组中的下一个元素，并对剩余的未排序元素重复该过程。
5. 继续这个过程，直到整个数组排序完毕。

#Suppose we have the following array:

arr = [64, 25, 12, 22, 11]

通过 1：

• 索引 0 和数组其余部分之间的最小元素是 11。
• 我们将 64 换成 11。

第一遍后的数组：[11, 25, 12, 22, 64]

通过2：

• 现在，关注从索引 1 开始的子数组。25、12、22、64 之间的最小元素是 12。
• 我们用 12 交换 25。

第二遍后的数组：[11, 12, 25, 22, 64]

通过 3：

• 25、22、64 之间的最小元素是 22。
• 我们用 22 交换 25。

第三遍后的数组：[11, 12, 22, 25, 64]

第 4 关：

• 子数组现在包含 25、64。由于它们已经按顺序排列，因此不需要交换。

最终排序数组：[11, 12, 22, 25, 64]

def selection_sort(arr):
    # Traverse through all array elements
    for i in range(len(arr)):
        # Find the minimum element in the remaining unsorted part
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

排序数组：[11, 12, 22, 25, 64]

选择排序的时间复杂度：

• 最佳情况：O(n²)

• 平均情况：O(n²)

• 最坏情况：O(n²)

尽管选择排序对于小型数据集表现良好，但对于较大的数组来说并不理想，因为它的时间复杂度为 O(n²)。然而，它很容易实现，并且在需要考虑内存的情况下非常有用，因为选择排序是就地的（不需要额外的内存）。

优点和缺点

优点：

• 易于理解和实施。

• 在小列表上表现良好。

• 不需要额外的内存，因为它对数组进行排序。

缺点：

• 由于 O(n²) 时间复杂度，对于大型数据集效率较低。

• 它不是一个稳定的排序算法，这意味着相等的元素可能无法保留它们相对于彼此的顺序。

以上是选择排序算法的详细内容。更多信息请关注PHP中文网其他相关文章！