写点什么

【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;}
复制代码


效果图:



<br/>👍 <br/>⭐️ <br/>✏️ <br/>



发布于: 刚刚阅读数: 3
用户头像

游坦之

关注

还未添加个人签名 2022-10-14 加入

还未添加个人简介

评论

发布
暂无评论
【C++】选择排序​_10月月更_游坦之_InfoQ写作社区