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

王春枝 , 王立柱

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

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

王春枝 , 王立柱

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

快速排序和堆排序是程序設(shè)計(jì)中的典型算法，但不易理解，因?yàn)樗鼈儍?nèi)含深刻的辯證思想。文章詳細(xì)論述這些算法中的辯證思想，旨在幫助學(xué)生高屋建瓴地把握這些算法。

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

0 引 言

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

1 快速排序算法

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

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

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

圖1 第1趟排序

第2趟排序：以49的左子樹元素序列的首元素27為基準(zhǔn)，將其分作左右兩部分[13]和[38]， 27是左子樹的根，如圖2（a）所示，圖2（b）是它的拓?fù)浣Y(jié)構(gòu)。

圖2 第2趟排序

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

第3趟排序：以49的右子樹元素序列的首元素76為基準(zhǔn)，將其分作左右兩部分[50,65]和[97]， 76是右子樹的根，如圖3（a）所示，圖3（b）是它的拓?fù)浣Y(jié)構(gòu)。

圖3 第3趟排序

第4趟排序：以76的左子樹元素序列的首元素50為基準(zhǔn)，將其劃分為左右兩個(gè)子集，左子集為空，50為子樹的根，如圖4（a）所示，圖4（b）是它的拓?fù)浣Y(jié)構(gòu)。圖4（b）的中序序列顯然是一個(gè)有序序列。

圖4 第4趟排序

快速排序完畢。

2 堆排序算法

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

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

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

（1）刪除存儲(chǔ)結(jié)構(gòu)中第一個(gè)元素，然后將最后一個(gè)元素移到首位，如圖5（b）所示。

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

圖5 小根堆的刪除過程

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

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

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

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

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

堆排序步驟如下[2]：

圖6 小根堆的插入過程

（1）模仿堆類的插人Insert方法，將數(shù)組調(diào)整為小根堆。因?yàn)橹挥幸粋€(gè)元素的數(shù)組為堆，所以從數(shù)組第2個(gè)元素到最后一個(gè)元素掃描，每掃描一個(gè)元素，相當(dāng)于向堆中插人一個(gè)元素，這時(shí)的數(shù)組可能不再是小根堆，需要將數(shù)組向上調(diào)整為小根堆。

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

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

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

3 結(jié) 語

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

[1] 王立柱, 王春枝. 計(jì)算機(jī)科學(xué)與編程導(dǎo)論[M] 北京: 清華大學(xué)出版社, 2015: 119-122.

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

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

（編輯：宋文婷）

1672-5913(2017)01-0159-03

G642

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

王春枝，女，教授，研究方向?yàn)橛?jì)算機(jī)應(yīng)用、計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)遠(yuǎn)程教育，chunzhiwang@ vip．163．com。