选择排序

简介: 选择排序

selectionSort

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

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

算法步骤

#include<iostream>

usingnamespacestd;

//选择排序,参数为数组和数组长度

voidselectionSort(intarr[],intn){

   for(inti=0;i<n;i++){

       //找到[i,n)范围内的最小值坐标,初始最小值坐标为i

       intminIndex=i;

       for(intj=i+1;j<n;j++){

           if(arr[j]<arr[minIndex])

               minIndex=j;

       }

       //交换坐标值

       swap(arr[i],arr[minIndex]);

   }

}

intmain(){

   inta[10]={10,9,8,7,6,5,4,3,2,1};

   selectionSort(a,10);

   for(inti=0;i<10;i++)

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

   cout<<endl;

   return0;

}

//输出

//1 2 3 4 5 6 7 8 9 10

上述代码只能对int类型进行选择排序,设置为模板函数即可对任意类型进行排序:template<typename T>

//选择排序

template<typenameT>

voidselectionSort(Tarr[],intn){

   for(inti=0;i<n;i++){

       //找到[i,n)范围内的最小值坐标,初始最小值坐标为i

       intminIndex=i;

       for(intj=i+1;j<n;j++){

           if(arr[j]<arr[minIndex])

               minIndex=j;

       }

       //交换坐标值

       swap(arr[i],arr[minIndex]);

   }

}

操作符重载

当要对自定义的类或结构体进行选择排序时,就需要重构operator<,因为判断元素的大小是依靠操作符<。因为要输出,所以也要对输出操作符<<进行重载

//Student.h

#ifndef STUDENT_H

#define STUDENT_H

#include<iostream>

#include<string>

usingnamespacestd;

structStudent{

   stringname;

   intscore;

   booloperator< (constStudent&otherStudent){

       returnthis->score<otherStudent.score;

   }

   //重构operator<<

   friendostream&operator<< (ostream&os,constStudent&student){

       os<<"Student:"<<student.name<<" "<<student.score<<endl;

       returnos;

   }

};

#endif

//selectionSort.cpp

#include<iostream>

#include "Student.h"//引入Student.h

usingnamespacestd;

//选择排序

template<typenameT>

voidselectionSort(Tarr[],intn){

   for(inti=0;i<n;i++){

       //找到[i,n)范围内的最小值坐标,初始最小值坐标为i

       intminIndex=i;

       for(intj=i+1;j<n;j++){

           if(arr[j]<arr[minIndex])

               minIndex=j;

       }

       //交换坐标值

       swap(arr[i],arr[minIndex]);

   }

}

intmain(){

   Studentd[4]={ {"D",90},{"C",100},{"B",95},{"A",95} };

   selectionSort(d,4);

   for(inti=0;i<4;i++)

       cout<<d[i];

   cout<<endl;

   return0;

}

/*从小到大排序

Student:D 90

Student:B 95

Student:A 95

Student:C 100

*/

操作符本质上是函数,分为成员函数和全局函数

成员函数

去掉friend,那么operator <<变为成员函数,需要使用对象来调用,成员函数默认含有隐藏的参数this

this:是一个pointer(指针),指向函数调用者,即对象。(谁调用我,我就指向谁)

通过this指针获取对象中的成员,可以this->name,也可以(*this).name,也可以name,因为this是可以省略的

//  ostream& operator << (this,ostream& os)

//                  ||

   ostream&operator<< (ostream&os){

       os<<"Student:"<<this->name<<" "<<(*this).score<<endl;

       returnos;

   }

//d[i]为一个对象,对象调用operator<<函数,参数为cout

d[i].operator<<(cout);

同样的成员函数operator<,调用时arr[j]<arr[minIndex]=arr[j].operator<(arr[minIndex]),C++中操作符都是作用于左边

全局函数

友元函数operator <<不是成员函数,因此不需要对象来调用即可使用

   friendostream&operator<< (ostream&os,constStudent&stu){

       os<<"Student:"<<stu.name<<" "<<stu.score<<endl;

       returnos;

   }

//全局函数直接调用,参数为cout和Student的对象d[i]

operator<<(cout,d[i]);

//与下行代码效果相同

cout<<d[i];

目录
相关文章
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1255 5
|
1天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1275 87
|
12天前
|
云栖大会
阿里云云栖大会2025年9月24日开启,免费申请大会门票,速度领取~
2025云栖大会将于9月24-26日举行,官网免费预约畅享票,审核后短信通知,持证件入场
1821 13