资料结构与演算法

《资料结构与演算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章排序資料結構與演算法徐熊健7.1排序的考量7.2排序演算法7.3排序究竟可以有多快目錄排序(sorting)是個既重要又經常用到的運算。舉凡資料的整理、搜索，都有排序資料的需求；對排序過的資料運用二元搜尋演算法進行搜索，往往是各類搜索問題的核心技術；各種商用的資料庫，也以排序和搜尋的速度相互較量；許多組合問題(combinatorialproblem)的解決，都以排序為其前置運算(pre-processing)，例如在加權圖形中找最小延展樹的Kruskal演算法，就得先對所有的邊，依其距離做由小至大的排序處理。第七章排序排序的目的是將相同性質的資料，依其順序關係（由小至大

2、或由大至小）排列；隊伍中的身高關係、英文字典中的字詞順序、公司薪資的高低、事件發生具今的遠近、…，都是可以排序的資料。在關聯式資料庫(relationaldatabase)的記錄(record)中，每個欄位也都可能是排序的對象；一般而言主欄位(keyfield)大都會加以排序，以方便使用者觀察或取用所要的記錄資料。當資料涉及資料庫時，我們皆以主鍵欄代表整筆紀錄。7.1排序的考量依據排序資料存放位置的不同，排序的範疇可分成兩種：(1)內部排序法(internalsorting)：指的是資料全部在主記憶體中。(2)外部排序法(externalsorting)；指的是主記憶體中只存放

3、部分資料，而大部分的資料皆在外部記憶體(如，硬碟、磁帶…..檔案)中。7.1排序的考量兩種排序方式在存取速度方面，有顯著的差異：內部排序法的資料存取皆在主記憶體中進行，而主記憶體屬於隨機存取設備(randomaccessdevice)，遂速度較快。而外部排序法的資料大多在硬碟、磁帶等循序存取設備(sequentialaccessdevice)中，所以存取速度會慢上許多，處理資料的量通常也比內部者大上許多。本章的討論以內部排序法為主。7.1排序的考量7.2.1挑選排序法7.2.2插入排列法7.2.3氣泡排序法7.2.4Shell排序法7.2.5合併排序法7.2.6快速排序法7.2

4、.7基數排序法7.2.8堆積排序法7.2排序演算法欲排序的n筆資料先行存放在一維陣列中，利用n次迴圈完成排序—在第i次迴圈時，挑出第i小的資料將之與陣列中第i筆資料對調—即可重整陣列使成為由小至大排序的數列。在2.2.1節中也提及其時間複雜度為O(n2)。挑選演算法除了幾個局部變數(localvariable)外，並不需額外的空間。某個資料在找比它小的資料時，會有資料對調的動作；這個動作可能使得值相同值的資料，不再保持原來的相對先後順序，遂排選排序法不具穩定性。7.2.1挑選排序法插入排序法(insertionsort)是將排序的過程視為：將未排序的資料遂一插入已排序的部分資料

5、中。下圖7-1顯示了第i筆資料插入前i-1筆已排序資料的動作：7.2.2插入排列法演算法7-1插入排序法輸入：整數陣列data，長度為n輸出：排序陣列data，若itarget)&&(j>0))5{a[j]=a[j-1];6j--;7}8a[j]=target;9}7.2.2插入排列法7.2.3氣泡排序法當資料希望以小至大（由上而下）排序時，氣泡排序法(bubblesort)要求相鄰的兩元素要維持「上小下大」

6、的順序關係；相鄰的兩元素會互相比較大小，將較大的資料往下放。一旦大資料被放到最下面，他應比其它所有資料都大，他肯定是最大的資料；於是同法找出次大、第三大、…；即可完成排序的動作。氣泡之名實來自其大資料向下沉去、或小資料向上浮出，好似重物投入水中下沉，而其擠壓之氣泡往上竄出之現象。演算法7-2氣泡排序法輸入:整數陣列data，共計n筆資料輸出:排序陣列data，若i0;i--)2for(j=1;j<=i;j++)3if(data[j-1]>data[j])4swap(data[j-1],data[

7、j]);7.2.3氣泡排序法Shell排序法是由DonaldShell所提出的，由上一節氣泡排序法的經驗可知：即令原來的資料尚未完全排序完成，但若有不少資料已位在它們在排序完成時應處的位置上，則可減少資料搬移的動作。直覺來想：資料的大小順序符合者愈多，可減少資料交換的個數，對所有資料的排序愈有利。Shell排序法的概念即希望以「分組排序、逐次增加大小順序符合的資料個數」來進行排序：資料先行分成小組，各小組進行排序，由於各組內的資料已依大小順序排放，則整體再併成大組排序時，應可獲得減少資料交換