选择排序算法 – 范的资源库

什么是选择排序？

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

算法步骤

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

#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 usagearr = [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²) 时间复杂度，对于大型数据集效率较低。