选择排序-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

选择排序

简介: 选择排序

selectionSort

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

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

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

算法步骤

#include<iostream>

using namespace std;

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

void selectionSort(int arr[],int n){

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

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

        int minIndex=i;

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

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

                minIndex=j;

        }

        //交换坐标值

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

    } 

}

int main(){

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

    selectionSort(a,10);

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

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

    cout << endl;

    return 0;

}

//输出

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

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

//选择排序

template<typename T>

void selectionSort(T arr[],int n){

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

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

        int minIndex=i;

        for(int j=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>

using namespace std;

struct Student{

    string name;

    int score;

    bool operator < (const Student& otherStudent){

        return this->score<otherStudent.score

    }

   //重构operator<<

    friend ostream& operator << (ostream& os,const Student& student){

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

        return os;

    }

};

#endif

//selectionSort.cpp

#include<iostream>

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

using namespace std;

//选择排序

template<typename T>

void selectionSort(T arr[],int n){

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

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

        int minIndex=i;

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

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

                minIndex=j;

        }

        //交换坐标值

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

    } 

}

int main(){

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

    selectionSort(d,4);

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

        cout << d[i];

    cout<<endl;

    return 0;

}

/*从小到大排序

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;

        return os;

    }

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

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

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

全局函数

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

    friend ostream& operator << (ostream& os,const Student& stu){

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

       return os;

    }

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

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

//与下行代码效果相同

cout << d[i];

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章