Python实现选择排序算法

选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序的实现比较简单，首先从待排序的序列中找到最小元素，将它与序列的 个元素交换位置；然后，在剩下的序列中找到最小元素，将它与序列的第二个元素交换位置；以此类推，最终得到一个有序的序列。

以下是Python实现选择排序算法的代码：

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        min_idx = i
        
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

以上代码中，arr 是待排序的数组。我们首先通过 len(arr) 获取数组的长度，即待排序元素的个数。接下来，我们使用两层循环实现选择排序算法。外层循环控制待排序的元素数量，内层循环从当前位置的下一个位置开始，寻找更小的元素，并记录下标。如果找到更小的元素，就将其下标赋值给 min_idx。在内层循环结束后，我们将 arr[i] 和 arr[min_idx] 的值交换，即将最小的元素放在序列的起始位置。最后，返回有序的数组 arr。

下面是一个使用选择排序算法的例子：

arr = [5, 8, 2, 1, 6, 3, 4, 9, 7]
sorted_arr = selection_sort(arr)
print(sorted_arr)

运行以上代码输出的结果为 [1, 2, 3, 4, 5, 6, 7, 8, 9]。可以看到，选择排序算法成功地将无序的数组 [5, 8, 2, 1, 6, 3, 4, 9, 7] 转换成有序的数组 [1, 2, 3, 4, 5, 6, 7, 8, 9]。

选择排序算法的时间复杂度是 O(n^2)，其中 n 是待排序元素的个数。由于选择排序算法是一个**不稳定**的排序算法，即相同大小的元素在排序后可能会交换位置，所以在排序元素中包含相同大小的元素时，可能会产生错误的排序结果。因此，在实际应用中，为了确保排序的稳定性，我们一般不会选择选择排序算法。而是使用其他更高效的排序算法，比如快速排序、归并排序等。