Sorting Algorithm

程式的基本功

Heap Sort

　　是一高等排序演算法，為selection sort的改良。
基本概念：和selection sort一樣將數列分成未排序及已排序兩部分，將未排序的資料中找出最大(最小)的元素插入至已排序好的數列中的最右(左)端。
而Heap sort的改良是將選擇最大(最小)的方法改進，使用Heap Tree做資料結構，搜尋時最多只需搜尋樹根到葉的路徑，不再需要搜尋整個未排序的數列，大大增進速率。

Principle

  • 將數列分成兩部分：未排序及已排序。
    • 　
  • 使用Heap Tree做資料結構

    • Complexity

    Time complexity:
    Best.Worst.Average case皆為O(n log n)。

    1. Buttom-Up方式建立Heap花O(n)。
    2. 執行(n-1)回合，每一回合花O(log n)時間作"類似"Delete MAX in Heap之動作 =>O(n log n)
    ->總共花O(n)+O(n log n) =>O(n log n)

    Space complexity:
    　　O(1)。

    運算流程

    1. 先將input data以Buttom-up方法建立MAX-Heap。
    2. 執行(n-1)回合，每一回合執行類似Delete MAX的動作選出元素，再將選出之元素放入已排序好數列的最右端。
      即將root與當時sublist之”the last node”作swap。
      針對剩下Data進行調整成符合MAX-Heap工作。

    Stable vs. Unstable sort

    Unstable。
    ex: Input:5,5*,1
    　　 5
    　　/　\
    　 5*　1
    　Output:1,5*,5

    簡易code

    1. Adjust(tree,i,n)　　//調整以i為root之子樹成MAX-Heap tree:[1...n] of data
    2. HeapSort(tree,n)

    I. Adjust(tree,i,n)　　//tree是array[1...n]
    調整以i為root之subtree成為Heap
    { done=false;
    　r=tree[i];　//r:保存
    　k=tree[i].key;　//k:編號
    　j=2*i;　　//在i的左child
    　while(j<=n)and(not done) do
    　{ if j<n then
    　　　if tree[j].key<tree[j+1].key then
    　　　{　　j=j+1;
    　 }
    　　if k>=tree[j].key then
    　　{done=True;
    　　}
    　　else
    　　{ tree[j/2]=tree[j];
    　　　j=2*j;
    　　}
    　}
    　tree[j/2]=r;
    }

    簡易code

    II. HeapSort(tree,n)　　//排序tree:[1...n]
    {for i=n/2 down to 1 do
    　Adjust(tree,i,n);
    　for i=n-1 down to 1 do
    　{swap(tree[1],tree[i+1]);
    　　Adjust(tree,1,i);
    　}
    }