选择排序

Posted on Edited on In

题目描述
选择排序是一种简单直观的排序算法。它的工作原理是每次从未排序的部分选出最小（或最大）的元素，放到已排序部分的末尾，直到所有元素均排序完毕。

输入格式
输入共 2 行，第一行是一个整数 n，表示数组的长度。第二行包含 n 个整数，表示待排序的数组。

输出格式
输出共 1 行，包含 n 个整数，表示排序后的数组（升序排列）。

数据范围
1 ≤ n ≤ 1000
-1000 ≤ 数组元素 ≤ 1000

输入样例：

1
2
6
8 4 2 5 1 7

输出样例：

1
1 2 4 5 7 8

注意事项

  • 选择排序的时间复杂度为 O(n²)，空间复杂度为 O(1)。
  • 选择排序是不稳定的排序算法。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    // 选择排序
    for (int i = 0; i < n - 1; i++)
    {
        int min_index = i; // 记录当前未排序部分中最小元素的索引
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[min_index])
            {
                min_index = j;
            }
        }
        // 将找到的最小元素与未排序部分的第一个元素交换
        if (min_index != i)
        {
            int temp = a[i];
            a[i] = a[min_index];
            a[min_index] = temp;
        }
    }
    
    // 输出排序后的数组
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    
    return 0;
}

时间复杂度

  • 时间复杂度：O(n²)，其中 n 为数组的长度。
  • 空间复杂度：O(1)。

代码解释

  • 我们使用两层循环来实现选择排序。外层循环控制已排序部分的末尾位置，内层循环在未排序部分中寻找最小元素。
  • 在每一轮中，我们从未排序部分（从i+1到n-1）找到最小的元素，并记录其索引。
  • 然后将找到的最小元素与未排序部分的第一个元素（即位置i的元素）交换位置。
  • 重复上述过程，直到整个数组排序完成。