王春枝 , 王立柱

（湖北工业大学 计算机学院， 湖北 武汉 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）是它的拓扑结构。……