选择法排序pta

选择排序（Selection Sort）是一种简单直观的排序算法。其基本思想是：首先在未排序的序列中找到最小（大）元素，然后将其存放到序列的起始位置，接着再从剩余未排序的元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

具体实现过程如下：

1. 从序列中找到最小元素，存放到排序序列的起始位置

2. 从剩余未排序元素中继续寻找最小元素，存放到已排序序列的末尾

3. 重复步骤2，直到所有元素均排序完毕

下面是选择排序的示例代码实现（以升序排序为例）：

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]
    return arr

时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。虽然时间复杂度较高，但是选择排序在实现上比较简单，适用于小规模数据的排序。