选择排序

〇、返回

一、概述

选择排序是一种简单直观的比较类排序算法。它的基本思想是：每次从未排序的部分找到最小（或最大）元素，放到已排序序列的末尾。

二、工作原理

1. 初始状态：无序区为 R[1..n]，有序区为空。

2. 第 i 趟排序 (i=1,2,..., n-1)：

    在当前无序区 R[i.. n] 中选出关键字最小的记录 R[k]。

    将它与无序区的第 1 个记录 R[i] 交换，使 R[1..i] 和 R[i+1..n] 分别为记录个数增加 1 个和减少 1 个的有序区和无序区。

3. n-1 趟结束：数组有序。

三、算法步骤

1. 首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。

2. 然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

3. 重复第二步，直到所有元素均排序完毕。

四、代码实现（C++）

#include<bits/stdc++.h>

using namespace std;

int main() {

    int n;

    cin>>n;

    vector<int> a(n);

    for (int i=0;i<n;i++) {        // 读入数组

        cin>>a[i];

    }

    for (int i=0;i<n-1;i++) {        // 枚举要操作的元素

        int pos=i;

        for (int j=i+1;j<n;j++) {        // 记录从这个位置起第一个小于该元素的元素的下标

            if (a[j]<a[pos]) {

                pos=j;

            }

        }

        if (pos!=i) {        // 交换元素

            swap(a[i], a[pos]);

        }

    }

    for (int i=0;i<n;i++) {        // 输出排序后的数组

        cout<<a[i]<<" ";

    }

    cout<<"\n";

    return 0;

}

五、时空复杂度及稳定性

时间复杂度

最坏情况时间复杂度：O($n^2$)（每次都需要遍历剩下的所有元素来找到最小值）

最好情况时间复杂度：O($n^2$)（即使数组已经是有序的，也需要进行相同的比较次数）

平均情况时间复杂度：O($n^2$)

空间复杂度

选择排序的空间复杂度为 O(1)，因为它只需要一个额外的临时变量来进行交换操作。

稳定性

选择排序是一种不稳定的排序算法。例如，在 [5, 8, 5, 2, 9] 中，第一次选择最小值时会将第一个5与2交换，导致原始顺序被破坏。

六、总结

选择排序算法简单且易于理解，但在大多数情况下并不是最优的排序算法，特别是在数据量较大的情况下。然而，它对于理解排序算法的基本概念和原理非常有帮助。在实际应用中，更高效的排序算法如快速排序、归并排序等更为常用。