辩证内含丰富的算法举例

王春枝 , 王立柱

（湖北工业大学 计算机学院， 湖北 武汉 430068）

辩证内含丰富的算法举例

王春枝 , 王立柱

（湖北工业大学 计算机学院， 湖北 武汉 430068）

快速排序和堆排序是程序设计中的典型算法，但不易理解，因为它们内含深刻的辩证思想。文章详细论述这些算法中的辩证思想，旨在帮助学生高屋建瓴地把握这些算法。

快速排序；堆排序；二叉树；遍历

0 引 言

快速排序和堆排序看似线性问题，实则是非线性问题，而且综合运用多种方法才能求解。以快速排序为例，它需要综合运用线性连续存储、二叉树、前序遍历和中序遍历的概念。综合运用这些概念，包含着丰富的辩证思想。这些算法一般是数据结构中的典型算法，但很多教材特别是语言教材都在数据结构之前讲授这些内容，给学生的理解带来很大困难。我们有必要具体解释它们固有的辩证内容。

1 快速排序算法

快速排序算法的基本思想是利用线性连续存储结构，在二叉树的前序遍历基础上建立二叉树，最终的有序序列是这棵二叉树的中序序列[1]。

以数组元素[49,38, 65, 97, 76, 13, 27, 50]为例，实施快速排序。

第1趟排序：以首元素49为基准，把数组元素分为左右两部分，左部分不大于基准，右部分不小于基准，如图1（a）所示。基准49相当于根，左右两部分[27,38, 13]和[76, 97, 65, 50]相当于左右子树的节点。图1（b）是它的拓扑结构。

图1 第1趟排序

第2趟排序：以49的左子树元素序列的首元素27为基准，将其分作左右两部分[13]和[38]， 27是左子树的根，如图2（a）所示，图2（b）是它的拓扑结构。

图2 第2趟排序

这时，49的左子树中序序列已经有序。

第3趟排序：以49的右子树元素序列的首元素76为基准，将其分作左右两部分[50,65]和[97]， 76是右子树的根，如图3（a）所示，图3（b）是它的拓扑结构。

图3 第3趟排序

第4趟排序：以76的左子树元素序列的首元素50为基准，将其划分为左右两个子集，左子集为空，50为子树的根，如图4（a）所示，图4（b）是它的拓扑结构。图4（b）的中序序列显然是一个有序序列。

图4 第4趟排序

快速排序完毕。

2 堆排序算法

堆排序的关键是堆。堆是一种按照层次顺序连续存储的、特殊的完全二叉树，一般分大根堆和小根堆。我们以小根堆为例，小根堆的特点是每一个结点的键都不大于其左右孩子的键，或者说，从根到叶结点的任何路径上的键都是非减的，如图5（a）所示。

堆还是一种用非线性手段提高存取速度的优先级队列，它的主要操作是删除和插人。

小根堆的删除是首删，删除的是最小元素，这个元素是二叉树的根，即存储中的首元素。步骤如下：

（1）删除存储结构中第一个元素，然后将最后一个元素移到首位，如图5（b）所示。

（2）删除后结构可能不再是堆（但根的左右子树还是堆），需要向下调整为堆。调整的方法是将首元素即根不断与其左右孩子的较小者比较，若大于后者，则交换，直至恢复堆秩序，如图5（c）所示。

图5 小根堆的删除过程

向下调整算法的实质是向下起泡排序：在线性结构中，向下起泡排序是前驱和后继比较，但在堆结构中，前驱和后继的关系扩展为双亲和孩子的关系，而且后继不止一个，需要择其小者。

小根堆的插人是尾插，步骤如下：

（1）将新的数据元素插人数据的尾部，如图6（b）所示。

（2）插人后的数据可能不再是堆，需要向上调整为堆。调整的方法是将插人的数据元素不断与其双亲比较，若小于双亲，则交换，直至恢复堆秩序，如图6（c）所示。

向上调整算法的实质是向上起泡排序：在线性结构中，向上起泡排序是后驱和前继比较，但在堆结构中，后驱和前继的关系扩展为孩子和双亲的关系。

堆排序步骤如下[2]：

图6 小根堆的插入过程

（1）模仿堆类的插人Insert方法，将数组调整为小根堆。因为只有一个元素的数组为堆，所以从数组第2个元素到最后一个元素扫描，每扫描一个元素，相当于向堆中插人一个元素，这时的数组可能不再是小根堆，需要将数组向上调整为小根堆。

（2）将数组首元素和尾元素调换，数组元素个数减1（相当于删除首元素）;然后将缩小后的数组向下调整为小根堆。

（3）重复步骤（2），直到数组元素个数为0。

需要注意的是，利用小根堆排序，结果是降序序列。如果需要升序序列，可以仿照小根堆，建立大根堆。

3 结 语

所谓一个对象复杂，难以理解，是因为这个对象包含太多相互联系和相互作用的因素。用恩格斯的话讲：“事物是互相作用着的，并且在大多数情形下，正是忘记了这种多方面的运动和相互作用，阻碍我们的自然科学家去看清最简单的事物”[3]。要正确地理解和把握这些因素，就需要辩证思维，因为辩证思维不是别的，正是复杂对象中相互联系、相互作用的规律在头脑中的反映。

[1] 王立柱, 王春枝. 计算机科学与编程导论[M] 北京: 清华大学出版社, 2015: 119-122.

[2] 王立柱. 数据结构与算法[M]. 北京: 华章出版社, 2013: 129-131.

[3] 张建林, 王立柱. 马克思恩格斯哲学原著英汉对照选读[M]. 天津: 天津人民出版社, 2009: 179.

（编辑：宋文婷）

1672-5913(2017)01-0159-03

G642

湖北省教育厅项目“程序设计能力培养体系建设与实践”（2015294）；全国高等学校计算机教育研究会项目 “程序设计能力培养课程体系建设与实践”（MXF2016-2-5，ER2016004）。

王春枝，女，教授，研究方向为计算机应用、计算机网络和计算机远程教育，chunzhiwang@ vip．163．com。