r7-4 选择排序 分数 25 现请参照如下示意图,实现选择排序: selectionsort.png 输

选择排序是一种简单且直观的排序算法。它的基本思想是每一轮找出最小（或最大）的元素，然后与当前位置的元素进行交换，从而将最小（或最大）的元素放到正确的位置。下面以一个示意图来说明选择排序的具体步骤：

给定一个待排序的数组：[7, 3, 5, 9, 2]，我们需要将其按照非降序排列，即从小到大。

首先，在数组中选取最小的元素，也就是2。与第一个位置的元素7进行交换，即[2, 3, 5, 9, 7]。

接下来，在剩下的未排序部分中选取最小的元素，也就是3。与第二个位置的元素3进行交换，由于他们相同，所以数组保持不变，[2, 3, 5, 9, 7]。

然后，在剩下的未排序部分中选取最小的元素，也就是5。与第三个位置的元素5进行交换，即[2, 3, 5, 9, 7]。

再次，在剩下的未排序部分中选取最小的元素，也就是7。与第四个位置的元素9进行交换，即[2, 3, 5, 7, 9]。

最后，在剩下的未排序部分中选取最小的元素，也就是9。由于他已经在正确的位置上，不需要进行交换。所以最终得到有序数组：[2, 3, 5, 7, 9]。

选择排序的时间复杂度为O(n^2)，其中n为数组的长度。尽管如此，选择排序在一些特定情况下可能仍然是一个很好的选择。

相关问题

R7-1 选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，其基本思想是每次从未排序的序列中选择最小（或最大）的元素，放到已排序序列的末尾，直到所有元素都排序完成。

具体实现步骤如下：

1. 遍历数组，找到最小的元素，并记录其下标。

2. 将最小元素与数组第一个元素交换位置。

3. 从剩下未排序的元素中重复步骤1，直到所有元素都排序完成。

下面是选择排序的示例代码：

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)$。由于其时间复杂度较高，选择排序一般只适用于小规模数据的排序。

r7-3冒泡排序陕西理工大学

以下是r7-3冒泡排序陕西理工大学的Python实现：

# 输入样例
# 6 2 2 3 5 1 6 4
# 输出样例
# 2 1 3 4 5 6

n, *a = map(int, input().split())

for i in range(n - 1):
    for j in range(n - i - 1):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
    print(*a[:n - i - 1], end=' ')
print(a[-1])