欢迎来到天天文库
浏览记录
ID:43598475
大小:358.00 KB
页数:36页
时间:2019-10-11
《资料结构与演算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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排序法的概念即希望以「分組排序、逐次增加大小順序符合的資料個數」來進行排序:資料先行分成小組,各小組進行排序,由於各組內的資料已依大小順序排放,則整體再併成大組排序時,應可獲得減少資料交換
此文档下载收益归作者所有