电脑的基本操作ppt课件.ppt

《电脑的基本操作ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter13排序13.1氣泡排序13.2選擇排序13.3插入排序13.4合併排序13.5快速排序13.6堆積排序13.7二元樹排序13.8謝耳排序13.9基數排序Chapter13排序排序的方式可以分成兩種：內部排序（internalsort）如果記錄是在主記憶體（mainmemory）中進行分類，則稱之。外部排序（externalsort）假若記錄太多，以致無法全部存於主記憶體，需借助輔助記憶體，如磁碟或磁帶來進行分類，則稱之。2Chapter13排序除了上述內部排序和外部排序之區別外，也可以分成下列兩類：比較排序（comparativesort）如

2、果排序方式是比較整個鍵值（keyvalue）的話，則稱之。分配排序（distributivesort）假使是一次只比較鍵值的某一位數，此類稱之。3Chapter13排序存於檔案（file）中的記錄（record），可能含有相同的鍵值。對於兩個鍵值k(i)=k(j)的記錄r(i)和r(j)，如果在原始檔案中，r(i)排在r(j)之前；而在排序後，檔案中的r(i)仍在r(j)之前，則稱此排序具有穩定性（stable）。反之，如果r(j)在r(i)之前，則稱此排序為不穩定（unstable）。亦即表示當兩個鍵值一樣時並不需要互換，此稱為穩定排序，反之，即使鍵值相同

3、仍需互換者，則稱為不穩定排序。413.1氣泡排序氣泡排序（bubblesort）又稱為交換排序（interchangesort）。相鄰兩個相比，假使前一個比後一個大時，則互相對調。通常有n個資料時需要做n-1次掃瞄，一次掃瞄完後，資料量減少1，當沒有對調時，就表示已排序好了。513.1氣泡排序例如有5個資料，分別是18,2,20,34,12以氣泡排序的步驟如下：613.1氣泡排序假設鍵值是12,18,2,20,34，則需要幾次掃瞄呢?713.1氣泡排序由於在第三次掃瞄，沒有做互換的動作，因此可知資料已排序好，不用再比較了。我們可利用一變數加以判斷是否要繼續下

4、一次的掃描與比較。氣泡排序是stable，最壞時間與平均時間為O(n2)，所需要額外空間也很少。813.2選擇排序選擇排序（selectionsort）首先在所有的資料中挑選一個最小的放置在第一個位置（因為由小到大排序），再從第二個開始挑選一個最小的放置於第二個位置.....，一直下去。913.2選擇排序例如有5個記錄，其鍵值為18,2,20,34,12。利用選擇排序，其做法如下：選擇排序跟氣泡排序一樣是stable，最壞時間與平均時間都是O(n2)，所需要額外空間亦很少。1013.3插入排序插入排序（insertionsort）乃將加入的資料置於適當的位置

5、，如下圖所示：1113.3插入排序在j的每個步驟將加入的資料，找出其適當的位置如j=4時，加入25，則需將39和45往後移，再將25放在12的後面。餘此類推。插入排序是stable的性質，最壞時間和平均時間均為O(n2)，所需額外空間很少。1213.4合併排序合併排序(mergesort)乃是將兩個或兩個以上已排序好的檔案，合併成一個大的已排序好的檔案。1313.4合併排序假使在一堆無排序的資料，我們可以先將它們一對一合併，再來二對二合併，三對三合併，如下圖所示，假設有下列8個鍵值18,2,20,34,12,32,6,16。1413.4合併排序從上圖大致可以

6、發現最後合併的動作，乃是和上述將兩個已排序好的資料加以合併而成。合併分類是stable，最壞時間與平均時間均為O(nlog2n)。所需的額外空間與檔案大小成正比。1513.5快速排序快速排序（quicksort）又稱為劃分交換排序（partitionexchangesorting）。就平均時間而言，快速排序是所有排序中最佳的。假設有n個R1,R2,R3,...,Rn，其鍵值為K1,K2,K3,...,Kn。1613.5快速排序快速排序法其步驟如下：以第一個記錄的鍵值k1做基準K。由左至右i=2,3,...,n，一直找到ki>K。由右至左j=n,n-1,n

7、-2,...,2，一直找到kj

8、節點來得大或等於。而利用heap來排序的方法稱為堆積