排序的相关知识.ppt

《排序的相关知识.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、排序的相關知識排序(Sorting)是指將一群資料，按特定規則調換位置，使資料具有某種次序關係(遞增或遞減)。例如資料庫內可針對某一欄位進行排序，而此欄位稱為「鍵(key)」，欄位裡面的值我們稱之為「鍵值(value)」。排序資料的移動方式在排序的過程中，資料的移動方式可分為「直接移動」及「邏輯移動」兩種。「直接移動」是直接交換儲存資料的位置，而「邏輯移動」並不會移動資料儲存位置，僅改變指向這些資料的輔助指標的值。兩者間優劣在於直接移動會浪費許多時間進行資料的更動，而邏輯移動只要改變輔助指標指向的位置就能輕易

2、達到排序的目的。排序的好處1.資料較容易閱讀。2.資料較利於統計及整理。3.可大幅減少資料搜尋的時間。排序的分類排序依執行時所使用的記憶體可分為：內部排序：排序的資料量小，可以完全在記憶體內進行排序。外部排序：排序的資料量無法直接在記憶體內進行排序，而必須使用到輔助記憶體(如硬碟)。排序演算法的分析排序演算法的好壞可由以下幾點決定：演算法是否穩定時間複雜度（Timecomplexity）空間複雜度（Spacecomplexity）演算法是否穩定穩定的排序是指資料在經過排序後，兩個相同鍵值的記錄仍然保持原來的次

3、序，如下例中7左的原始位置在7右的左邊（所謂7左及7右是指相同鍵值一個在左一個在右），穩定的排序(StableSort)後7左仍應在7右的左邊，不穩定排序則有可能7左會跑到7右的右邊去。例如：原始資料順序：7左297右6穩定的排序：267左7右9不穩定的排序：267右7左9時間複雜度當資料量相當大時，排序演算法所花費的時間就顯得相當重要。排序演算法的時間複雜度可分為最好情況(BestCase)、最壞情況(WorstCase)及平均情況(AverageCase)。最好情況就是資料已完成排序，例如原本資料已經完成

4、遞增排序了，如果再進行一次遞增排序所使用的時間複雜度就是最好情況。最壞情況是指每一鍵值均須重新排列，簡單的例子如原本為遞增排序重新排序成為遞減，就是最壞情況空間複雜度空間複雜度就是指演算法在執行過程所需付出的額外記憶體空間。例如所挑選的排序法必須藉助遞迴的方式來進行，那麼遞迴過程中會使用到的堆疊就是這個排序法必須付出的額外空間。另外，任何排序法都有資料對調的動作，資料對調就會暫時用到一個額外的空間，它也是排序法中空間複雜度要考慮的問題。排序法所使用到的額外空間愈少，它的空間複雜度就愈佳。例如氣泡法在排序過程中

5、僅會用到一個額外的空間，在所有的排序演算法中，這樣的空間複雜度就算是最好的。內部排序法排序名稱排序特性簡單排序法1.氣泡排序法(BubbleSort)(1)穩定排序法(2)空間複雜度為最佳，只需一個額外空間O(1)2.選擇排序法(SelectionSort)(1)不穩定排序法(2)空間複雜度為最佳，只需一個額外空間O(1)3.插入排序法(InsertionSort)(1)穩定排序法(2)空間複雜度為最佳，只需一個額外空間O(1)4.謝耳排序法(ShellSort)(1)穩定排序法(2)空間複雜度為最佳，只需一

6、個額外空間O(1)高等排序法1.快速排序法(QuickSort)(1)不穩定排序法(2)空間複雜度最差O(n)最佳O(log2n)2.堆積排序法(HeapSort)(1)不穩定排序法(2)空間複雜度為最佳，只需一個額外空間O(1)氣泡排序法氣泡排序法又稱為交換排序法，是最簡單的排序法之一。將資料放在同一陣列中，由第一個元素開始，比較相鄰的陣列元素大小，若大小順序有誤，則對調後再進行下個元素的比較。如此掃瞄過一次之後就可確保最後一個元素是正確的。接著再進行第二次掃瞄，直到完成排序。氣泡排序法分析最壞清況及平均情

7、況均需比較：(n-1)+(n-2)+(n-3)+…+3+2+1=n(n-1)/2次；時間複雜度為O(n2)，最好情況只需完成一次掃瞄，發現沒有做交換的動作則表示已經排序完成，所以只做了n-1次比較，時間複雜度為O(n)。由於氣泡排序為相鄰兩者相互比較對調，並不會更改其原本排列的順序，所以是穩定排序法。只需一個額外的空間，所以空間複雜度為最佳。此排序法適用於資料量小或有部份資料已經過排序。改良氣泡排序法傳統氣泡排序法有個缺點是：不管資料是否已排序完成都會執行n*(n-1)/2次，而我們可以藉由在程式中加入一判斷

8、式加以判斷何時可以提前中斷程式，又可得到正確的資料選擇排序法選擇排序法是從所有待排序的資料中找出最小(或最大)鍵值，將該筆記錄與第一筆記錄對調後，再從第二筆以後的資料中重覆做一樣的動作，直到完成排序為止。選擇排序法分析無論是最壞清況、最佳情況及平均情況都需要找到最大值(或最小值)，因此其比較次數為：(n-1)+(n-2)+(n-3)+…+3+2+1=n(n-1)/2次；時間複雜度為O(n2)由於選擇