演算法筆記(二) | Heap sort and Quick sort實作in Java

Coding-X的課堂筆記(二)

Published in

Code Da

6 min readAug 14, 2019

O(n log n):堆積排序法(Heap sort)

有些先備知識要先跟大家說，這邊的Heap sort是先以MaxHeap來整理出一個從大到小的Heap ，再用Heap sort從小到大的排序。那可能會聽不太懂，所以這邊簡單說明，MaxHaep在每個subtree 中，父節點都比自己的子節點大，但同一層的subtree不會比較大小，而Heapsort從小排到大可以想像成，從索引1開始到矩陣索引結束，都是從小排到大，那下面會詳細說明做法。

二元堆積(Binary Heap)

Binary Heap有二個特性:

第一個是Binary Heap可以視為一個Complete binary tree，那就可以用以下的公式去尋找child和parent:

Left child= index([i*2]);

Right child = index([i*2+1]);

Parent = index([⌊i/2⌋]);(向下取整)

如下圖(一)index(2)為例:

Left child是index(4);

Right child是index(5);

parent是index(1);

第二個特徵是以index(i)為subtree的root，那可以分為二類:

(一)Maxheap: 每一個subtree中，parent的數值會比所有的child的數值還要大，見圖(一)。

(二)Minheap:每一個subtree中，parent的數值會比所有的child的數值還要小。

最後，Binary heap的同一階層的Left child和Right chlid並不需要比較大小，只需要和它們的root做比較即可。

要滿足Binary heap的「parent-child」之關係，只要矩陣中index(0)的位置閒置，從index(1)開始存放資料如圖(一)，即可使用矩陣來表示Binary Heap。下面介紹如何建構Max heap。

最大堆積(MaxHeapify)

那MaxHeapify()主要是從上到下，去執行Maxheap的定義，root的值會大於兩個child的值，重複執行，直到所有的點都被檢查完。

在程式碼裡，會先初設3個變數，left 、right 、largest如下:

int left = root * 2;int right = (root * 2) + 1;int larget = root;

只要最大的不是root，就會去改寫largest的值，然後去交換最大的值和root的位置，之後可能調換過來後，新的root值可能還比parent大，所以要往上找(見圖二)。另一方面，舊的root的值，可能也會比原本largest值的位置下方的child還要小，所以也要往下找(見圖三)。

if (left <= length && array[left] > array[largest]) { // 長度要大於等於child的節點,可以防止超過矩陣的長度largest = left;}if (right <= length && array[right] > array[largest]) {largest = right;}if (root != largest) {Swap(array, largest, root);if(root > 1){Maxheapify(array, root / 2, length-1);//往上找}Maxheapify(array, largest, length-1);//往下找}

堆積排序法(Heap Sort)

經過上面的處理後，我們得到了一個Max heap的矩陣，那Max heap有一個很大的特點，就是頂端(索引1)是最大的，那我們把索引1和最後一個節點做交換，然後隱藏最後一個節點，那因為使用遞迴呼叫MaxHeapify()，那這個矩陣就要重新執行Maxheap，等到調整完後，再重複一次，直到做到index(2)為止(見圖四)。

public static int[] Heapsort(int[] array) {BulidMaxheap(array);int size = array.length-1;for (int b = array.length-1; b >= 2; b--) {Swap(array, 1, b);size--;Maxheapify(array, 1, size);}return array;}

貼心提醒要開啟旁邊的file裡面才有另一個class喔。

附上程式碼讓大家參考喔 (*´∀`)~♥

O(n log n):快速排序法(Quick sort)

快速排序法是一個最壞狀況時間複雜度是O(n²)的排序法，但只要基準點(Pivot)選得好，時間複雜度就會降到O(n log n)，那選基準點方式很多，這邊介紹的是從左邊(index 0)開始選基準點的方法。

運行概念:

實際上就是先選好基準點後，用2個指標(一個會在頭、一個會在尾)去紀錄索引，再開始去比較誰比基準大和小，當找到一個大的時候，會等另一個指標找到小的(見圖五)，反之亦然，然後去做位置的交換，到最後會分為比基準大的一群和比基準小的一群，在把基準點插在中間(見圖六)，對左右方做遞迴，重複剛剛的方式，直到結束。