王春枝 , 王立柱

（湖北工業(yè)大學 計算機學院， 湖北 武漢 430068）

辯證內(nèi)含豐富的算法舉例

王春枝 , 王立柱

（湖北工業(yè)大學 計算機學院， 湖北 武漢 430068）

快速排序和堆排序是程序設計中的典型算法，但不易理解，因為它們內(nèi)含深刻的辯證思想。文章詳細論述這些算法中的辯證思想，旨在幫助學生高屋建瓴地把握這些算法。

快速排序；堆排序；二叉樹；遍歷

0 引 言

快速排序和堆排序看似線性問題，實則是非線性問題，而且綜合運用多種方法才能求解。以快速排序為例，它需要綜合運用線性連續(xù)存儲、二叉樹、前序遍歷和中序遍歷的概念。綜合運用這些概念，包含著豐富的辯證思想。這些算法一般是數(shù)據(jù)結構中的典型算法，但很多教材特別是語言教材都在數(shù)據(jù)結構之前講授這些內(nèi)容，給學生的理解帶來很大困難。我們有必要具體解釋它們固有的辯證內(nèi)容。

1 快速排序算法

快速排序算法的基本思想是利用線性連續(xù)存儲結構，在二叉樹的前序遍歷基礎上建立二叉樹，最終的有序序列是這棵二叉樹的中序序列[1]。

以數(shù)組元素[49,38, 65, 97, 76, 13, 27, 50]為例，實施快速排序。

第1趟排序：以首元素49為基準，把數(shù)組元素分為左右兩部分，左部分不大于基準，右部分不小于基準，如圖1（a）所示?；鶞?9相當于根，左右兩部分[27,38, 13]和[76, 97, 65, 50]相當于左右子樹的節(jié)點。圖1（b）是它的拓撲結構。

圖1 第1趟排序

第2趟排序：以49的左子樹元素序列的首元素27為基準，將其分作左右兩部分[13]和[38]， 27是左子樹的根，如圖2（a）所示，圖2（b）是它的拓撲結構。

圖2 第2趟排序

這時，49的左子樹中序序列已經(jīng)有序。

第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 堆排序算法

堆排序的關鍵是堆。堆是一種按照層次順序連續(xù)存儲的、特殊的完全二叉樹，一般分大根堆和小根堆。我們以小根堆為例，小根堆的特點是每一個結點的鍵都不大于其左右孩子的鍵，或者說，從根到葉結點的任何路徑上的鍵都是非減的，如圖5（a）所示。

堆還是一種用非線性手段提高存取速度的優(yōu)先級隊列，它的主要操作是刪除和插人。

小根堆的刪除是首刪，刪除的是最小元素，這個元素是二叉樹的根，即存儲中的首元素。步驟如下：

（1）刪除存儲結構中第一個元素，然后將最后一個元素移到首位，如圖5（b）所示。

（2）刪除后結構可能不再是堆（但根的左右子樹還是堆），需要向下調(diào)整為堆。調(diào)整的方法是將首元素即根不斷與其左右孩子的較小者比較，若大于后者，則交換，直至恢復堆秩序，如圖5（c）所示。

圖5 小根堆的刪除過程

向下調(diào)整算法的實質(zhì)是向下起泡排序：在線性結構中，向下起泡排序是前驅(qū)和后繼比較，但在堆結構中，前驅(qū)和后繼的關系擴展為雙親和孩子的關系，而且后繼不止一個，需要擇其小者。

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

（1）將新的數(shù)據(jù)元素插人數(shù)據(jù)的尾部，如圖6（b）所示。

（2）插人后的數(shù)據(jù)可能不再是堆，需要向上調(diào)整為堆。調(diào)整的方法是將插人的數(shù)據(jù)元素不斷與其雙親比較，若小于雙親，則交換，直至恢復堆秩序，如圖6（c）所示。

向上調(diào)整算法的實質(zhì)是向上起泡排序：在線性結構中，向上起泡排序是后驅(qū)和前繼比較，但在堆結構中，后驅(qū)和前繼的關系擴展為孩子和雙親的關系。

堆排序步驟如下[2]：

圖6 小根堆的插入過程

（1）模仿堆類的插人Insert方法，將數(shù)組調(diào)整為小根堆。因為只有一個元素的數(shù)組為堆，所以從數(shù)組第2個元素到最后一個元素掃描，每掃描一個元素，相當于向堆中插人一個元素，這時的數(shù)組可能不再是小根堆，需要將數(shù)組向上調(diào)整為小根堆。

（2）將數(shù)組首元素和尾元素調(diào)換，數(shù)組元素個數(shù)減1（相當于刪除首元素）;然后將縮小后的數(shù)組向下調(diào)整為小根堆。

（3）重復步驟（2），直到數(shù)組元素個數(shù)為0。

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

3 結 語

所謂一個對象復雜，難以理解，是因為這個對象包含太多相互聯(lián)系和相互作用的因素。用恩格斯的話講：“事物是互相作用著的，并且在大多數(shù)情形下，正是忘記了這種多方面的運動和相互作用，阻礙我們的自然科學家去看清最簡單的事物”[3]。要正確地理解和把握這些因素，就需要辯證思維，因為辯證思維不是別的，正是復雜對象中相互聯(lián)系、相互作用的規(guī)律在頭腦中的反映。

[1] 王立柱, 王春枝. 計算機科學與編程導論[M] 北京: 清華大學出版社, 2015: 119-122.

[2] 王立柱. 數(shù)據(jù)結構與算法[M]. 北京: 華章出版社, 2013: 129-131.

[3] 張建林, 王立柱. 馬克思恩格斯哲學原著英漢對照選讀[M]. 天津: 天津人民出版社, 2009: 179.

（編輯：宋文婷）

1672-5913(2017)01-0159-03

G642

湖北省教育廳項目“程序設計能力培養(yǎng)體系建設與實踐”（2015294）；全國高等學校計算機教育研究會項目 “程序設計能力培養(yǎng)課程體系建設與實踐”（MXF2016-2-5，ER2016004）。

王春枝，女，教授，研究方向為計算機應用、計算機網(wǎng)絡和計算機遠程教育，chunzhiwang@ vip．163．com。