【C++】选择排序

2022-10-24
山东
本文字数：1631 字
阅读完需：约 5 分钟

前言：✌ 作者简介：游坦之 ✌🏆 大学软件工程在读，希望学到真本领，经世致用 🏆📫 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀💬 人生格言：成好人，行好事，做儒猿💬🔥 如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

@TOC

🍸选择排序

🍖什么是选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

🍳举个栗子

对{29,10,14,8,8,20}进行选择排序，执行顺序如下：

首先需要设置两个变量，第一个变量，index 初始值为 0，代表已经排好多少个元素，第二个变量 temp，代表当前最小（大）的值。

第一趟 temp 设置为 i，经过一趟的比较，找到最小的值为 8，与 index 下的数进行交换，此时序列{8,10 14,29,8,20}，index 更新为 1;

第二趟重复上述过程，找到最小的值为 8，与 index 下的数据进行交换，此时序列{8,8,14,29,10,20}，index 更新为 2；

第三趟重复上述过程，找到最小的值为 10，与 index 下的数据进行交换，此时序列{8,8,10,29,14,20}，index 更新为 3；

第四趟重复上述过程，找到最小的值为 14，与 index 下的数据进行交换，此时序列{8,8,10,14,29,20}，index 更新为 4；

第五趟重复上述过程，找到最小的值为 20，与 index 下的数据进行交换，此时序列{8,8,10,14,10,19}，index 更新为 5；

index = n-1(n 为待排序元素的个数)；排序完成。

🥩伪代码

for(int i=0;i<n;i++){    int temp = i;    for(int j = index;j<n;j++)    {        if(a[temp]>a[j])        {            temp = j;        }    }    swap(a[temp],a[i]);    index++;}

复制代码

🍃见解

选择排序的核心思想即是在一个范围里（为排序的）找出最小或者最大的值，与范围的起始值进行交换，进行 n-1 躺，从而排序完整个集合。

选择排序的时间复杂度：由于需要排序 n-1 躺，每一趟又需要遍历 m 个元素，所以选择排序的时间复杂度即为 O(n2)。

比赛时，只能适合 10000 以内的数据，如果超出了这个数据，很可能会超时。

这里有一个技巧，就是在比赛的时候，可以避免使用 cin、cout，而使用 c 语言中的 printf、scanf，后者是比前者快很多的，当然前者也可以通过其他代码进行优化，但如果记不住，可以直接用 C 语言的输入输出，以提高通告的概率。

什么叫算法的稳定性：算法稳定性指的是在一组待排序记录中,如果存在任意两个相等的记录 R 和 S,且在待排序记录中 R 在 S 前,如果在排序后 R 依然在 S 前,即它们的前后位置在排序前后不发生改变,则称为排序算法为稳定的。

为什么选择排序是不稳定的？举个特例{10,8,10,4}，这四个值第一个 10 我们标记为 A10，第二个 10 我们标记为 B20，在第一次排序过程后序列变为{4,8,10,10}，A10 去了 B10 后面，和原来的相对位置不一样了，所以选择排序是不稳定的。

🥗牛刀小试

对{5,10,20,48,29,10}进行排序

#include <iostream>using namespace std;int n;int a[10010];int main(){    cin>>n;    for(int i=0;i<n;i++)    {        cin>>a[i];    }    int index = 0;    for(int i=0; i<n;i++)    {        int temp = i;        for(int j=index;j<n;j++)        {            if(a[temp]>a[j])            {                temp = j;            }        }        swap(a[temp],a[i]);        index++;        if(index==n)        {          break;    }    }    for(int i=0;i<n;i++)    {        cout<<a[i]<<" ";      }    return 0;}