当前课程知识点:C++语言程序设计进阶 >  第九章 模板与群体数据 >  排序 >  选择排序

返回《C++语言程序设计进阶》慕课在线视频课程列表

选择排序在线视频

选择排序

选择排序

选择排序的基本思想

9-18.png

例9-12 简单选择排序函数模板

template <class T>
void mySwap(T &x, T &y) {
    T temp = x;
    x = y;
    y = temp;
}

template <class T>
void selectionSort(T a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int leastIndex = i; 
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[leastIndex])
                leastIndex = j;
        mySwap(a[i], a[leastIndex]);
    }
}



下一节:交换排序

返回《C++语言程序设计进阶》慕课在线视频列表

选择排序课程教案、知识点、字幕

大家好

欢迎回来继续学习

C++语言程序设计

这一节我们来学习

选择排序

我们来看一个

选择排序里面的

最简单的一种方式

就是简单选择排序

这个算法的思想呢

就是从这个未排序序列中

每一次按照关键字的值

去选出一个数据来

放到已排序序列的末尾

那么选最大的

还是选最小的呢

取决于你要升序排列

还是降序排列

如果我们是希望

由小到大排列的话

那么每一次

就从这个待排序的序列中

经过比较

选出一个最小的元素

依次排在已排序序列的末尾

每次选一个

每次选一个

直到未排序系列里面的全部元素

都被选出来了

那么整个序列也就有序了

现在我们来看一下这个示意图

现在我们来看

还是以这个序列为例

5 4 10 20 12 3

那么这个简单选择排序的算法

它关键在于选择

每次要从这个未排序序列中

选出一个最小的元素来

依次排列在

已排序序列的最末尾的位置去

追加到已排序序列的最末尾

那么第一轮呢

显然我们应该选出这个3

怎么能选出这个最小的3呢

简单选择排序

用的是从头到尾比较一遍的办法

把这个序列的数据

一个一个进行比较

那比较一轮

肯定又找出那个最小的来了

那就把3取出来

那么这个时候怎么能把3

排到前面去呢

不用移动大量的数据

3和最前面的5进行交换就行了

这样3就放到了

已排序序列的末尾

那下一轮呢

就选出了4

那这个时候看到

4已经是在最头上的位置了

那就4

依然落在当前位置就可以了

接下来会选出这个5

5呢

我们需要把它排在4之后

也就是现在这个元素10

所在的位置

那这时候就把10拿出来

跟5交换一下

5就排到前面去了

那么接下来呢

再选出来的应该是10 12 20

依此类推

全部的元素都选完了呢

当然整个序列也就变成有序了

好 下面这个例题呢

就是一个

实现简单选择排序的函数模板

我们来看

这个程序上是怎么实现的

在选择排序中呢

我们经常需要用到一个

交换的功能

所以在这儿呢

我们单独写了一个mySwap

这个交换函数

用来交换两个参数x y

那接下来我们来看

这个函数模板里面

它也是排序

接受一个待排序的数组a

以及元素个数

选择了一个排序呢

是每一次从待排序序列中

选出一个最小的

放在已排序序列的末尾

也就是说待排序序列的头

因为它不用额外的空间

只用原来的数组

原地交换这样排序 对吧

那我们循环呢就是从0开始

到什么

到小于n-1

不用到最后一个

前面n-1个元素都确定了

最后一个元素

当然它就应该在最后了

那现在我们要用内层for循环

来选出当前的待排序序列中

最小的那个元素

首先我们就把最小元素的下标

初始化为i

就是开头这个位置

然后在这个循环中

每一次比较

一个一个元素依次比较

从第i+1个开始

到第n-1个

就是每次这样比较

发现更小的

就记下这个更小的元素

它的下标

这样内层for循环结束以后

这个listIndex里面放的

就是那个最小元素下标了

拿它跟ai进行交换就可以了

那这就是一个

简单选择排序的函数模板

C++语言程序设计进阶课程列表:

第七章 继承与派生

-导学

--导学

-继承的基本概念和语法

--继承的基本概念和语法

-第七章 继承与派生--继承的基本概念和语法习题

-继承方式

--继承方式简介及公有继承

--私有继承和保护继承

-第七章 继承与派生--继承方式

-基类与派生类类型转换

--基类与派生类类型转换

-第七章 继承与派生--基类与派生类类型转换

-派生类的构造和析构

--派生类的构造函数

--派生类的构造函数举例

--派生类的复制构造函数

--派生类的析构函数

--第七章 继承与派生--派生类的构造和析构

-派生类成员的标识与访问

--访问从基类继承的成员

--虚基类

-第七章 继承与派生--派生类成员的标识与访问

-小结

--小结

-综合实例

--第七章综合实例

-实验七

--实验七

-第七章讲义

第八章 多态性

-导学

--导学

-第八章 多态性--导学

-运算符重载

--运算符重载的规则

--双目运算符重载为成员函数

--单目运算符重载为成员函数

--运算符重载为非成员函数

-第八章 多态性--运算符重载

-虚函数

--虚函数

--虚析构函数

--虚表与动态绑定

-第八章 多态性--虚函数

-抽象类

--抽象类

--第八章 多态性--抽象类

-override与final

--override与final

-第八章 多态性--override与final

-小结

--第八章小结

-综合实例

--第八章综合实例

-实验八

--实验八

- 第八章讲义

第九章 模板与群体数据

-导学

--导学

-模板

--函数模板

--类模板

-第九章 模板与群体数据--模板

-线性群体

--线性群体的概念

-第九章 模板与群体数据--线性群体

-数组

--数组类模板

--例9-4数组类应用举例

-链表

--链表的概念与结点类模板

--链表类模板

-第九章 模板与群体数据--链表

-栈

--栈类模板

--栈类模板课后习题

--例9-9 栈的应用

--例9-9 栈的应用课后习题

-队列

--队列类模板

-第九章 模板与群体数据--队列

-排序

--排序概述

--插入排序

--选择排序

--交换排序

-第九章 模板与群体数据--排序

-查找

--查找

--查找课后习题

-小结

--小结

-综合实例

--综合实例

-实验九

--实验九

- 第九章讲义

第十章 泛型程序设计与C++标准模板库

-导学

--导学

-泛型程序设计及STL的结构

--泛型程序设计的基本概念

--STL简介

-第十章 泛型程序设计与C++标准模板库--泛型程序设计及STL的结构

-迭代器

--迭代器

-第十章 泛型程序设计与C++标准模板库--迭代器

-容器的基本功能与分类

--容器的基本功能与分类

-第十章 泛型程序设计与C++标准模板库--容器的基本功能与分类

-顺序容器

--顺序容器的基本功能

--顺序容器的特征

--顺序容器的插入迭代器与适配器

--第十章 泛型程序设计与C++标准模板库--顺序容器

-关联容器

--关联容器分类和基本功能

--集合

--映射

--多重集合和多重映射

-第十章 泛型程序设计与C++标准模板库--关联容器

-函数对象

--函数对象

--函数适配器

-算法

--算法

-小结

--第十章小结

-综合实例

--综合实例

-实验十

--实验十

- 第十章讲义

第十一章 流类库与输入/输出

-导学

--导学

-I/O流的概念及流类库结构

--I/O流的概念及流类库结构

-第十一章 流类库与输入/输出--I/O流的概念及流类库结构

-输出流

--输出流概述

--向文本文件输出

--向二进制文件输出

--向字符串输出

-第十一章 流类库与输入/输出--输出流

-输入流

--输入流概述

--输入流应用举例

--从字符串输入

-第十一章 流类库与输入/输出--输入流

-输入/输出流

--输入/输出流

-第十一章 流类库与输入/输出--输入/输出流

-小结

--小结

-综合实例

--综合实例

-实验十一

--实验十一

- 第十一章讲义

第十二章 异常处理

-导学

--第12章导学

-异常处理的思想与程序实现

--异常处理的思想与程序实现

-第十二章 异常处理--异常处理的思想与程序实现

-异常处理中的构造与析构

--异常处理中的构造与析构

-第十二章 异常处理--异常处理中的构造与析构

-标准程序库异常处理

--标准程序库异常处理

-第十二章 异常处理--标准程序库异常处理

-小结

--第12章小结

-综合实例

--综合实例

-实验十二

--实验十二

- 第十二章讲义

选择排序笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。