13.1 氣泡排序 13.2 選擇排序 13.3 插入排序 13.4 合併排序 13.5 快速排序

Slides:



Advertisements
Similar presentations
Software Learning Resource Service Platform CHAPTER 7 搜尋和排序 (Search and Sort) 1.
Advertisements

數數 8. 認識 100 以內的數 讓孩子仔細觀察表格,並說 出以下規律: 每行有 ___ 個數,前一個比 後一個少 ___ ; 每列有 ___ 個數;下一個比 上一個多 ___ ; 右斜看發現下一個數比上一 個數多 ___; 左斜看發現上一個數比下一 個數少 ___ ; 數一數,一位數有 ___.
1 第八章 深入探討樹狀結構. 2 目次 8.1 m-way 搜尋樹 8.2 B-tree 8.3 動動腦時間 8.4 練習題解答.
14 2 、 5 和 10 的整除性 1 © 明思出版有限公司 2 、 5 和 10 的整除性一 明思數學 4 上 B.
7.4 用矩阵初等行变换 解线性方程组 主要内容: 一.矩阵的行初等变换 二.用行初等变换求逆矩阵 三.用矩阵法求线性方程组.
使用C/C++語言 楊正宏 編著 全華科技圖書股份有限公司 印行.
Sort(排序) 授課者:驕芸.
新世代計算機概論 第15章 資料結構.
Chapter 5 樹狀結構.
第5章 排序与查找 PART A 《可视化计算》.
第十章 内部排序 10.1 概述 10.2 插入排序 直接插入排序 其他插入排序 希尔排序
課程名稱:程式設計 授課老師:________
第四章 數列與級數 4-1 等差數列與級數 4-2 等比數列與級數 4-3 無窮等比級數 下一頁 總目錄.
輔助記憶體.
第八章 排序 8-1 排序簡介 8-2 內部排序法 8-3 外部排序法.
課程名稱:資料結構 授課老師:_____________
第11章 資料結構 – 使用C語言的模組 11-1 資料結構的基礎 11-2 C語言的模組化程式設計 11-3 基本鏈結串列
排序 Sorting.
第9章 排序.
第十章 排序與搜尋.
Analysis of Sorting Algorithms
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
(Circular Linked Lists)
基數排序 (Radix Sort).
以下這個謎題無法透過宮摒除法完成解題。 但可透過「區塊宮摒除法」或「行列摒除法」完成 By TTHsieh
鄧姚文 資料結構 第六章:樹(Tree) 鄧姚文
Chapter 9 高度平衡二元搜尋樹 AVL Binary Search Tree
排序的相關知識 排序(Sorting)是指將一群資料,按特定規則調換位置,使資料具有某種次序關係(遞增或遞減)。
鄧姚文 資料結構 第九章:排序與搜尋 鄧姚文
基數排序法.
Chapter 8 排序 資料結構導論 - C語言實作.
Sorting 排序 Bubble Sort O(n2) Insert Sort Selection Sort Quick Sort
Chap3 Linked List 鏈結串列.
第一章 直角坐標系 1-1 數系的發展.
Chapter 11 B-tree 11.1 m-way 搜尋樹 11.2 B-tree.
Ch 3 Dynamic Programming (動態規劃).
如何赢一个机械键盘
第七章 資料排序 Sorting 版權屬作者所有,非經作者 同意不得用於教學以外用途.
Chap4 Tree.
北一女中 資訊選手培訓營.
第一章 直角坐標系 1-3 函數圖形.
Reference to FUNDAMENTALS OF DATA STRUCTURE IN C++
資料來源 2 網路過濾軟體之安裝說明 資料來源 2.
第8章 資料排序 資料結構設計與C++程式應用
Sorting in Linear Time.
小學四年級數學科 8.最大公因數.
第九章 排序 概述 插入排序 快速排序 交换排序(起泡排序) 选择排序 归并排序.
CH05. 選擇敘述.
第 十 章 排序(Sorting) 課程名稱:資料結構 授課老師:________ 2019/4/20.
資料結構與C++程式設計進階 樹狀結構(Tree) 講師:林業峻 CSIE, NTU 11/ 12, 2009.
蕭志明 老師 Algorithm(演算法) Ext:6779
蕭志明 老師 Algorithm(演算法) /FB:
Teacher: 郭育倫 Mail: 演算法 Teacher: 郭育倫 Mail:
Ogive plot example 說明者:吳東陽 2003/10/10.
C qsort.
程式設計-- Binary Search 通訊一甲 B 楊穎穆.
講師:郭育倫 第3章 基本資料結構 講師:郭育倫
6.1 樹狀結構的一些專有名詞 6.2 二元樹 6.3 二元樹的表示方法 6.4 二元樹的追蹤 6.5 引線二元樹 6.6 其它議題
Commando War ★★☆☆☆ 題組:Problem Set Archive with Online Judge
1-1 二元一次式運算.
資料表示方法 資料儲存單位.
程式設計--Quick Sort 通訊一甲 B 楊穎穆.
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
堆積(Heap Tree) 授課老師:蕭志明.
資料結構 老師:李崇明 助教:楊斯竣.
資料結構 老師:李崇明 助教:楊斯竣.
JAVA 程式設計與資料結構 第十九章 Sorting.
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
Chapter 4 Multi-Threads (多執行緒).
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
Presentation transcript:

13.1 氣泡排序 13.2 選擇排序 13.3 插入排序 13.4 合併排序 13.5 快速排序 Chapter 13 排序 13.1 氣泡排序 13.2 選擇排序 13.3 插入排序 13.4 合併排序 13.5 快速排序 13.6 堆積排序 13.7 二元樹排序 13.8 謝耳排序 13.9 基數排序

Chapter 13 排序 排序的方式可以分成兩種: 內部排序(internal sort) 如果記錄是在主記憶體(main memory)中進行分類,則稱之。 外部排序(external sort) 假若記錄太多,以致無法全部存於主記憶體,需借助輔助記憶體,如磁碟或磁帶來進行分類,則稱之。

Chapter 13 排序 除了上述內部排序和外部排序之區別外,也可以分成下列兩類: 比較排序(comparative sort) 如果排序方式是比較整個鍵值(key value)的話,則稱之。 分配排序(distributive sort) 假使是一次只比較鍵值的某一位數,此類稱之。

Chapter 13 排序 存於檔案(file)中的記錄(record),可能含有相同的鍵值。對於兩個鍵值 k(i) = k(j)的記錄 r(i) 和 r(j),如果在原始檔案中,r(i) 排在 r(j) 之前;而在排序後,檔案中的 r(i) 仍在 r(j) 之前,則稱此排序具有穩定性(stable)。反之,如果 r(j) 在 r(i) 之前,則稱此排序為不穩定(unstable)。亦即表示當兩個鍵值一樣時並不需要互換,此稱為穩定排序,反之,即使鍵值相同仍需互換者,則稱為不穩定排序。

13.1 氣泡排序 氣泡排序(bubble sort)又稱為交換排序(interchange sort)。 13.1 氣泡排序 氣泡排序(bubble sort)又稱為交換排序(interchange sort)。 相鄰兩個相比,假使前一個比後一個大時,則互相對調。 通常有n個資料時需要做n-1次掃瞄,一次掃瞄完後,資料量減少1,當沒有對調時,就表示已排序好了。

13.1 氣泡排序 例如有5個資料,分別是18, 2, 20, 34, 12以氣泡排序的步驟如下:

13.1 氣泡排序 假設鍵值是12, 18, 2, 20, 34,則需要幾次掃瞄呢?

13.1 氣泡排序 由於在第三次掃瞄,沒有做互換的動作,因此可知資料已排序好,不用再比較了。我們可利用一變數加以判斷是否要繼續下一次的掃描與比較。 氣泡排序是stable,最壞時間與平均時間為O(n2),所需要額外空間也很少。

13.2 選擇排序 選擇排序(selection sort)首先在所有的資料中挑選一個最小的放置在第一個位置(因為由小到大排序),再從第二個開始挑選一個最小的放置於第二個位置.....,一直下去。

13.2 選擇排序 例如有5個記錄,其鍵值為18, 2, 20, 34, 12。利用選擇排序,其做法如下: 13.2 選擇排序 例如有5個記錄,其鍵值為18, 2, 20, 34, 12。利用選擇排序,其做法如下: 選擇排序跟氣泡排序一樣是stable,最壞時間與平均時間都是O(n2),所需要額外空間亦很少。

13.3 插入排序 插入排序(insertion sort)乃將加入的資料置於適當的位置,如下圖所示:

13.3 插入排序 在j的每個步驟將加入的資料,找出其適當的位置如j=4時,加入25,則需將39和45往後移,再將25放在12的後面。餘此類推。 插入排序是stable的性質,最壞時間和平均時間均為O(n2),所需額外空間很少。

13.4 合併排序 合併排序(merge sort)乃是將兩個或兩個以上已排序好的檔案,合併成一個大的已排序好的檔案。

13.4 合併排序 假使在一堆無排序的資料,我們可以先將它們一對一合併,再來二對二合併,三對三合併,如下圖所示,假設有下列8個鍵值18, 2, 20,34, 12, 32, 6, 16。

13.4 合併排序 從上圖大致可以發現最後合併的動作,乃是和上述將兩個已排序好的資料加以合併而成。 13.4 合併排序 從上圖大致可以發現最後合併的動作,乃是和上述將兩個已排序好的資料加以合併而成。 合併分類是stable,最壞時間與平均時間均為O(nlog2n) 。所需的額外空間與檔案大小成正比。

13.5 快速排序 快速排序(quick sort)又稱為劃分交換排序(partition exchange sorting)。就平均時間而言,快速排序是所有排序中最佳的。假設有n個R1, R2, R3, ..., Rn,其鍵值為K1, K2, K3, ..., Kn。

13.5 快速排序 快速排序法其步驟如下: 以第一個記錄的鍵值k1做基準K。 13.5 快速排序 快速排序法其步驟如下: 以第一個記錄的鍵值k1做基準K。 由左至右 i = 2,3,...,n,一直找到ki > K。 由右至左 j = n, n-1, n-2, ..., 2,一直找到kj < K 。 當i<j 時Ri與Rj互換,否則R1與Rj互換。

13.5 快速排序 例如有十個記錄,其鍵值分別為39, 11, 48, 5, 77, 18, 70, 25, 55, 33,利用快速排序過程如下:

13.5 快速排序 此時在39的左半部之鍵值皆比39小,而右半部皆比39大。 13.5 快速排序 此時在39的左半部之鍵值皆比39小,而右半部皆比39大。 再利用上述方法將左半部與右半部排序,形成遞迴(recursive)。 快速排序是unstable,最壞時間是O(n2),平均時間是O(n log2n) 。

13.5 快速排序 全部排序過程如下所示:

13.6 堆積排序 堆積(heap)是一棵二元樹,其特性是每一父節點的資料都比它的兩個子節點來得大或等於。 13.6 堆積排序 堆積(heap)是一棵二元樹,其特性是每一父節點的資料都比它的兩個子節點來得大或等於。 而利用heap來排序的方法稱為堆積排序(heap sort)。 圖13-1之(a)符合 heap的定義, 而(b)則否。

13.6 堆積排序 如何將圖13-2變成heap的型態呢?

13.6 堆積排序 茲以圖13-2之二元樹說明之。 從 開始, A[10] = 25 < A[5] = 67 故不必換。 13.6 堆積排序 茲以圖13-2之二元樹說明之。 從 開始, A[10] = 25 < A[5] = 67 故不必換。 A[4] = 5,其最大子節點 A[8] = 58,因58 > 5, 故將A[4]與A[8]對調。

13.6 堆積排序 A[3] = 80與最大子節點A[7] = 62相比,因80 > 62,故不必調換。 13.6 堆積排序 A[3] = 80與最大子節點A[7] = 62相比,因80 > 62,故不必調換。 A[2] = 7,由於其小於 A[5] = 67, 故A[2]與A[5]對調, 然後A[5]又比A[10] 小再調換。

13.6 堆積排序 A[1] = 27,小於A[3] = 80,故A[1]與A[3]對調,然後A[3]又比A[7]小再做調換,故二元樹變為

13.6 堆積排序 不難看出已經變成heap了,第1個資料80最大,此時80與第10個7對調,對調之後,最後一個資料就固定不動了,下面調整時資料量已減少1個。 完成了將二元樹變為一棵樹heap之後,也可以利用上述的方法繼續調整之。

13.6 堆積排序 可是這種方去會浪費很多不必要的比較,因為除了第1個資料外,其餘的資料皆相同,因此可以先令第一個節點為父節點,然後比較左、右子節點,視那一個大,若右子節點大,則只要調整右半部即可;反之,調整左半部(因為不須調整的那半部已符合heap的規則了)。

13.6 堆積排序 此時a[1] = 80, A[2] = 67, a[3] = 62, A[4] = 58, A[5] = 25, A[6] = 18, A[7] = 27, A[8] = 5, A[9] = 24, a[10] = 7,當i =1時,樹根節點A[1]與A[10]對調,然後輸出A[10];i = 2,樹根節點與A[9]對調,然後輸出A[9],餘此類推。因此[i = 1]時,輸出80,原先堆積變成

13.6 堆積排序

13.6 堆積排序 此時左、右節點各為67和62,因此將67與父節點7對調,以同樣的方法調整左半部即可(因為67在 父節點的左邊), 而右半部不必做調整 (因右半段沒更動)。 調整後為

13.6 堆積排序 [i = 2],承i = 1

13.6 堆積排序 [i = 3]:承i = 2

13.6 堆積排序 [i = 4]:承i = 3

13.6 堆積排序 [i = 5]:承i = 4

13.6 堆積排序 [i = 6]:承i =5

13.6 堆積排序 [i = 7]:承i = 6

13.6 堆積排序 [i = 8]:承i = 7

13.6 堆積排序 [i = 9]:承i = 8 只剩下節點5,再將其輸出。 13.6 堆積排序 [i = 9]:承i = 8 只剩下節點5,再將其輸出。 此時已全部排序完成,順序為輸出80, 67, 62, 58, 27, 25, 24, 18, 7, 5

13.7 二元樹排序 二元樹排序(binary tree sort)乃是先將所有的資料建立成二元搜尋樹,再利用中序法來追蹤,步驟如下: 13.7 二元樹排序 二元樹排序(binary tree sort)乃是先將所有的資料建立成二元搜尋樹,再利用中序法來追蹤,步驟如下: 將第一個資料放在樹根。 進來的資料皆與樹根相比較,若比樹根大,則置於右子樹;反之,置於左子樹。 二元搜尋樹建立完後,利用中序法追蹤,即可得到由小至大的排序資料。

13.7 二元樹排序

13.7 二元樹排序

13.7 二元樹排序 最後利用中序法來追蹤就可排序(由小至大)完成。

13.8 謝耳排序 假設有9個資料,分別是18, 2, 20, 34, 12, 32, 6, 16, 25, 10。謝耳排序(shell sort)方法如下: 先將所有的資料分成Y = (9/2)部份,則Y = 4,Y為劃分數,其中1, 5, 9 是第一部份;2, 6屬於第二部份;3, 7是第三部份;4, 8是第四部份。 每一循環的劃分數是Y,皆是上一循環二分數除2,即Yi+1 = Yi/2,最後一個循環的劃分數為1。

13.8 謝耳排序 先比較每一部份的前兩個,如[1:5],[2:6],[3:7],[4:8] 。 13.8 謝耳排序 先比較每一部份的前兩個,如[1:5],[2:6],[3:7],[4:8] 。 前兩個比較完成後,再比較每一部份的第二個和第三個,將較小的放入第二個,放入後還要和第一個相比較,若比第一個小,則需要調換。

13.8 謝耳排序

13.9 基數排序 基數排序(radix sort)又稱為bucket sort或bin sort。 13.9 基數排序 基數排序(radix sort)又稱為bucket sort或bin sort。 它是屬於distribution sort。基數排序是依據每個記錄的鍵值劃分為若干單元,把相同的單元放置在同一箱子。 基數排序是stable,所需的平均時間是O(n logr m) 。

13.9 基數排序 然後利用LSD的基數排序,此處所採取的基數為10,第1 次依每個鍵值最右邊的數字,放在對應的箱子,其情形如下所示:

13.9 基數排序

13.9 基數排序 然後將每一箱的記錄,由F(i)開始,0 < i < r,連接成一鏈結串列,如下所示: 13.9 基數排序 然後將每一箱的記錄,由F(i)開始,0 < i < r,連接成一鏈結串列,如下所示: 同樣的做法,再以每一鍵值由最右邊起的第二位數字為準,將之放置於對應的箱子。

13.9 基數排序

13.9 基數排序 上圖所形成的鏈結串列如下: 最後再以每一鍵值由最右邊起第三位數字為準,將之放入其所對應的箱子。

13.9 基數排序

13.9 基數排序 最後所形成的鏈結串列為 此時排序已告完成。