Python实现选择排序算法详解及其代码示例

选择排序是一种简单且直观的排序算法，其核心原理在于每次从未排序的部分中找出最小（或最大）的元素，并将其放置到已排序部分的末尾，从而逐步构建有序序列。在Python中，选择排序的实现过程如下： 1. **基本步骤**： - 定义一个名为`selection_sort`的函数，该函数接收一个列表（数组）作为输入参数。 - 获取列表的长度，用作循环迭代次数的上限。 - 使用一个外层循环`for i in range(n)`，这里的`n`是列表长度，表示当前已经排序的部分。 - 内层循环`for j in range(i+1, n)`，用于在未排序部分查找最小元素。 - 在内层循环中，如果发现`arr[j]`比`arr[min_index]`小（或大，取决于选择最小或最大），则更新`min_index`为`j`的值。 - 当内层循环结束，将`arr[min_index]`与`arr[i]`进行交换，确保已找到的最小元素被移到正确位置。 - 当外层循环完成后，整个列表即被排序。 2. **时间复杂度**： - 选择排序的时间复杂度是O(n^2)，其中n是列表的长度。这是因为无论输入数据如何，都需要进行n次遍历，每次遍历又需要比较n-i次，总比较次数为n*(n-1)/2，与n^2等价。 3. **示例代码**： ```python def selection_sort(arr): n = len(arr) for i in range(n): 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] # 交换操作 示例应用： arr = [64, 25, 12, 22, 11] selection_sort(arr) print("排序后的数组：", arr) ``` 上述代码将输出：`[11, 12, 22, 25, 64]`，这是经过选择排序处理后的有序数组。 选择排序适用于数据规模较小或者对算法实现效率要求不高的情况，但由于其较高的时间复杂度，对于大规模数据的排序不如其他更高效的排序算法，如快速排序、归并排序等。然而，由于其实现简单，选择排序在教学和理解排序算法基础概念时具有很高的价值。