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

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

插入排序在线视频

插入排序

插入排序

插入排序的基本思想

插入排序的示意图

9-17.png

例9-11 直接插入排序函数模板

template <class T>
void insertionSort(T a[], int n) {
    int i, j;
    T temp;

    for (int i = 1; i < n; i++) {       
        int j = i;
        T temp = a[i];
        while (j > 0 && temp < a[j - 1]) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = temp;
    }
}



下一节:选择排序

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

插入排序课程教案、知识点、字幕

大家好

欢迎继续回来学习

C++语言程序设计

接下来我们来学习

插入排序

我们来学习插入排序里面

最简单的一种排序

就是直接插入排序

它的算法的基本思想就是

从待排序序列

也就是无序的这个数据系列中

每一次依次拿出一个元素来

插入到

已排序序列里面的合适的位置

使得插入这个数据以后

已排序序列

仍然维持它的原来有序

一个一个地从未排序序列中

拿出元素来插入到

已排序序列的合适位置

直到未排序序列的元素

全部拿完了

那么整个序列

就完全变成有序的了

现在我们来看

这个插入排序的示意图

假设初始状态

我们有这样一组数据

5 4 10 20 12 3

它是无序的

现在我们要按照由小到大的次序

来排列这一组数据

也就是说要对它进行排序

这里呢

我们用直接插入排序的办法

那这个算法呢

它首先假设

第一个数据5

就是已排序序列的初始状态

它就一个数

认为它是有序的

当然也没什么问题

那接下来的任务

就是将从4开始到3

这剩下的

存在于无序的

未排序序列中的数据

一个个依次取出来

插入到合适的位置去

第一次我们先取出4来

4应该往哪儿插呢

我们从已排序序列的最末尾

开始比较

现在就一个数

拿4跟5比较一下

4比5要小

所以把它插入到5的前面

当我们把4拿出来的时候

看这个位置已经空出来了

所以5可以挪到后面

4插进去

接下来呢

就是拿出10

10跟已排序序列

最末尾的元素比较

它比5要大

所以它插入在5后面

10就落在当前的位置了

同样拿20来

要往里面插入

比较的结果也是

20就落在当前位置了

再下面一个元素是12

12跟20比较

12要比20小

所以无论将来12插入到哪儿

20都要往后移一个位置

所以20先后移

然后12再跟前一个元素比较

跟10比较

12比10大

所以呢

12就应该落在当前

空出来的这个位置

12就插入进去了

最后呢 还剩一个3

3拿出来以后跟20比较

20要往后移

跟12比较 12也要往后移

一个一个比较

它们都比3要大

所以的现在的元素都后移了

再往前走没有了

整个序列到头了

这个时候呢

就意味着3

在当前的位置落下

它放在最头上了

这样呢

一个未排序序列到此为止

就全部变成已排序的有序序列了

接下来呢

我们就来看

用程序怎么样实现

这个直接插入排序的过程

这里呢

我们不是写了一个普通的函数

而是写了一个函数模板

也就是说

它可以适用于

多种不同类型数据排序

当然了

这个排序算法中我们要看

它都有哪些运算

如果我们想用这个函数模板

去对不同类型的数据

进行排序的话

必须这个类型能够进行

函数体里面规定的这些运算

才可以

在这个直接插入排序函数模板中

我们看

这个它的函数模板的参数

是T类型的

也就是说

它可以

对任何任意类型的数据序列

进行排序

但是是不是

真的任意类型的数据序列

都可以用这个进行排序呢

那我们排序中还用到了

比如说赋值运算

用到了比较关系运算

这些运算是不是可以用在

你指定的类型上

这个我们使用的时候要注意

如果是对基本类型的数据

进行排序

没有问题

如果是对类的对象进行排序

那么这个类应该重载过

赋值运算符

应该重载过关系运算符

这样才可以

好 那看这个函数的数据参数呢

有一个数组

还有呢

数组元素个数

现在看

主要的排序

在这个for循环中进行

那么插入排序

就是假设首元素

也就是a0

是已排序序列的初始状态

那需要插入的元素呢

就是从下标为1的元素开始

一个个往里面插入

首先呢

可以这个循环就从1开始

到最后一个元素

第n-1个元素

那这里呢

我们需要把要插入的这个数据ai

从它的空间中取出来

复制到一个临时空间temp里面然后接下来

我们要用一个while循环

做什么事情呢

移动数据

这个循环里面用到了

j来控制下标

那j的初始状态就是i

那看每一轮循环做了什么

将a j-1里面的数据

移动到aj里面去

什么情况下这样移动呢

首先j大于0

这是还没有到头

从后往前比较 还没有到头

然后这个temp要小于a j-1

也就是这种情况下

a j-1才需要往后移

只要这种情况满足

就继续循环

每一个循环完了以后j-1

什么时候发现这个temp

不小于a j-1了

或者j达到0了

就说明当前位置

就是应该插入temp里面

数据的位置了

所以就将temp里面的数据

放在当前位置就可以了

这个程序非常简单

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

-综合实例

--综合实例

-实验十二

--实验十二

- 第十二章讲义

插入排序笔记与讨论

也许你还感兴趣的课程:

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