Page 130 - 高中 信息技术 选择性必修1 数据与数据结构

第五章 数据结构的应用

内部排序的方法很多，按照排序过程中所用策略的不同，通常分为五大类：插入排
序、选择排序、交换排序、归并排序和基数排序。其中，交换排序又包含冒泡排序和快速

排序，都是常用的排序算法。冒泡排序是一种简单、常见的排序算法，适合初学者学习；
快速排序是对冒泡排序的改进，它是目前内部排序中平均速度最快的排序算法，也是20世

纪十大算法之一。本教科书主要讨论冒泡排序、快速排序的基本思想和算法实现。
3．排序的存储结构

排序的方法很多，通常都要进行两种基本操作：
（1）比较两个元素关键字的大小。

（2）根据比较结果，将元素从一个位置移到另一个位置。
广东教育出版社
其中，第（1）种操作对大多数排序方法来说都是必要的，第（2）种操作可通过改变

元素的存储方式避免，比如采用链表存储结构存储的数据元素。
从操作角度看，排序是线性结构的一种操作，待排序元素可以用顺序存储结构和链

式存储结构来存储。在顺序存储结构中，待排序元素按自然顺序存放在连续的一块内存
空间中，元素之间的次序关系由其存储位置决定，所以排序过程中一定要移动元素；在

链式存储结构中，待排序元素按原始次序链接起来，排序时只需要修改链表指针，不用
移动元素。

本教科书除特殊说明外，排序所采用的存储结构均为顺序结构，即用数组存储。

5.3.2 冒泡排序

1．冒泡排序的基本思想

冒泡排序（Bubble Sort）是一种简单的交换排序算法，它是通过交换相邻的两个数据
元素，逐步将待排序列变成有序序列。它的基本思想如下：

（1）假设待排序元素有n个，从第一个元素开始，依次交换相邻的两个逆序元素，直
到最后一个元素为止，当第一趟排序结束，就会将最大（小）的元素移动到序列的末尾。

（2）然后按照以上方法进行第二趟排序，次大（小）的元素将会被移动到序列的倒
数第二个位置。

（3）依次类推，经过n-1趟排序后，整个元素序列就成了一个有序（升序或降序）的
序列。

每趟排序过程中，值小（大）的元素向前移动，值大（小）的元素向后移动，就像气
泡一样向上升，因此将这种排序方法称为冒泡排序。

例5：假设有五个元素的待排序列为25、10、17、37、13，将此序列按升序排序的冒

泡排序过程如图5-7所示。

122 122

21X2204.indd 122 2019/9/26 13:53:39