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

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

交换排序在线视频

交换排序

交换排序

交换排序的基本思想

最简单的交换排序方法——起泡排序

9-19.png

对具有n个元素的序列按升序进行起泡排序的步骤:

例9-13 起泡排序函数模板

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

template <class T>
void bubbleSort(T a[], int n) {
    int i = n – 1;
    while (i > 0) {
      int lastExchangeIndex = 0;
      for (int j = 0; j < i; j++)
        if (a[j + 1] < a[j]) {
         mySwap(a[j], a[j + 1]);
         lastExchangeIndex = j;
        }
       i = lastExchangeIndex;
    }
}



下一节:查找

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

交换排序课程教案、知识点、字幕

大家好

欢迎回来继续C++语言程序设计

这一节我们来学习交换排序

我们来学习交换排序中

最简单的一种叫起泡排序

交换排序的基本思想呢

就是按照某种比较规则

两两比较这个序列中的元素

如果发现他们的次序关系

不符合我们最终的要求

那么就把它换一下

当然

不同的交换排序算法呢

会按不同的规则

来对数据元素进行比较

那最简单的一个办法呢

就是依次两两比较

相邻元素依次两两比较

这就是起泡排序

我们来看一下

这个起泡排序的图示

在这个示例中呢

我们用这样一组数据

8 5 2 4 3

来演示

这个起泡排序的这么一个过程

我们希望按照

由小到大的次序排列

也就是最后要形成

2 3 4 5 8

这样一个序列

那起泡排序它的思想是什么呢

就是相邻的数据元素两两比较

如果次序不合适就交换

那现在我们把这个数据序列

竖着写

好 我们就看到

首先8和5比较

这时候8和5需要交换

因为5比较小 8比较大

8要往小交换 5要往上升

然后8再跟2比较

2又上升 8又下降

8继续再跟4比较

4上升 8下降

8再跟3比较

3上升 8沉底

所以经过第一趟

这个结果我们看到

最大的元素8沉底了

而小的元素呢

都依次往上升了一个

好 接下来下一趟

还是做同样的比较

只不过这一次

已经沉底的这个8

就不用再参与比较了

5和2比较

2上升 5下降

5和4比较

4上升 5下降

5和3比较

3上升 5下降

经过第二趟5又沉底了

现在沉底两个元素了

继续还要进行

就是2跟4比较

那么2本来就小 4比较大

这一个没有发生交换

4跟3比较

3比较小 交换到上面去

4往下沉

这一趟又沉底了一个4

那么接下来再比较下一趟

2跟3比较

这一次没有发生交换

那么这个就是很形象的一个说法

起泡排序

小的数据像气泡一样往上升

那么最大的数据每次下沉

那这样的起泡排序的算法

大家想想看

如果你拿到的这个数据序列

一开始就有序

或者已经大部分有序了

你还要进行这么多趟吗

其实就不用了

起泡排序呢

如果有n个元素

那么最多进行n-1趟比较和交换

但是如果

这个序列本来就已经有序

或者大部分有序了

我们就没有必要完全得

走完这n-1趟比较和交换

因为

如果某一趟比较之后

没有发生任何交换的话

就说明整个数据序列已经有序了

这个时候就可以停止这个过程了

接下来呢

我们还是以函数模板的方式

来实现这个起泡排序的算法

这是

这个起泡排序的函数模板的代码

在起泡排序中呢

也大量要用到元素之间的交换

所以还是将交换

单独写为一个独立的函数模板

这个起泡排序思想就是

相邻的数据元素两两比较

次序不合适就交换

一轮一轮地走

每一轮一个最大的沉底

小的往上升

好 那怎么控制

还要不要进行下一轮的比较

和交换呢

这里用这个变量i来控制

i的初始值是n-1

然而一开始第一轮总是要做的

我们先进去看看什么时候

它就不用交换了

好 这里要保存一个

lastExchangeIndex

就是最后一次发生交换的

那个元素的下标要记下来

为什么要记它呢

一会就看到了

现在我们进到内层for循环中

两两比较进行交换

这个呢从0开始

到i-1为止

就是第i轮循环

不用把所有元素都交换掉

都比较一遍

因为最后面的元素

已经是最大的了

如果是由小到大排序的话

所以每一轮它就是下标控制

从0开始到i-1

这样两两比较

a j+1跟a j比较

如果大小标的数据更小的话

那么升序排列它就

如果要求升序排列

它就不满足要求了

如果要求降序排序

那你把这个变成大于号就行了

这个我们假设是要由小到大排序

好 次序不合适呢

就调用mySwap交换这两个元素

交换完了以后

要存下刚才最后交换的

这个元素的下标

当这内层for循环执行完了以后

将这个lastexchangeIndex

赋值给i

这是最后一次交换这个下标

然后呢

这个while循环就要看

如果i是大于0的

就说明刚才这一趟发生了交换

应该继续再做下一趟

如果它等于0了

那就不需要进行下一趟交换了

那么大家呢

也可以说我做一个简单的

外层循环控制它

一共走n-1轮

内层循环控制它两两比较

那样对于一些基本有序的

或者是完全有序的序列呢

就要做好多冤枉的比较

它又不需要交换 对吧

那么用这样的方式

去控制有些对于基本有序的

或者说刚排序了

走了两轮以后

已经就有序了

这样的序列呢

就不必继续去比较和交换了

而且这个i呢

记下了lastExchangeIndex

它还可以控制内层这个for循环

比较到哪个元素就为止

还可以控制这一点

当然我们也可以用另外一种方式

用true false
来记录有没有发生交换

那么那个记录呢

就不能控制内层循环

已执行到哪儿为止

这个大家可以仔细琢磨琢磨

然后可以把这里面的一些算法

按照你自己的想法

做一些不同的修改

看看它的效率呢

可能会有少许的差别

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章小结

-综合实例

--综合实例

-实验十二

--实验十二

- 第十二章讲义

交换排序笔记与讨论

也许你还感兴趣的课程:

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