排序演算法 3

今天來介紹快速排序法跟堆積排序法

快速排序法

快速排序法是選擇數列中一個數值為基準點(pivot)，然後將所有比基準點小的數放在基準點左邊成左數列，將所有比基準點大的數放在基準右邊成右數列，然後將左右數列再取一個基準點做一樣的事情，直到左右數列剩下一個數值或沒有數值，執行效率因為第一次需要比數列的量(n)，後續是拆數列對半去排序(log n)，平均O(n log n)。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
int Partition(vector<T> &vec, int left, int right)
{
    int pivot = vec[right];
    int i = left - 1;
    for (int j = left; j < right; j++)
    {
        if (vec[j] < pivot)
        {
            i++;
            swap(vec[i], vec[j]);
        }        
    }
    i++;
    swap(vec[i], vec[right]);
    return i;
}

template <typename T>
void QuickSort(vector<T> &vec, int left, int right)
{
    if (left < right)
    {
        int pivot = Partition(vec, left, right);
        QuickSort(vec, left, pivot - 1);
        QuickSort(vec, pivot + 1, right);
    }    
}

int main(int argc, char const *argv[])
{
    vector<int> vec = {9, 5, 88, 64, 1, 58, 15, 13, 77, 51, 58};
    QuickSort(vec, 0, vec.size() -1);
    cout << "QuickSort: " << endl;
    for (auto &v : vec)
    {
        cout << v << endl;
    }

    return 0;
}

堆積排序法

堆積排序法是用堆積樹(Heap Tree)的概念，堆積樹是個二元樹，父節點最多有兩個子節點，父節點若小於子節點，為最小堆積(Min Heap)；反之，若父節點大於子節點，為最大堆積(Max Heap)，作法是先建立最大或最小堆積樹，然後將最上層的父節點移除，再重新建一次堆積樹，重複這樣的動作直到堆積樹沒有剩餘節點，得到的數列就是排序過的，執行效率是建立堆積樹是O(n)，將樹上每個點移除O(n - 1)，加上樹高執行O(log n)，所以總執行效率是Ο(n log n)

template <typename T>
void Heapify(vector<T> &vec, int N, int i)
{
    // root
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < N && vec[left] > vec[largest])
    {
        largest = left;
    }

    if (right < N && vec[right] > vec[largest])
    {
        largest = right;
    }

    if (largest != i)
    {
        swap(vec[i], vec[largest]);

        Heapify(vec, N, largest);
    }    
}

template <typename T>
void HeapSort(vector<T> &vec, int N)
{
    for (int i = N / 2 - 1; i >= 0; i--)
    {
        Heapify(vec, N, i);
    }
    for (int i = N - 1; i > 0; i--)
    {
        swap(vec[0], vec[i]);

        Heapify(vec, i, 0);
    }    
}

int main(int argc, char const *argv[])
{
    vector<int> vec = {9, 5, 88, 64, 1, 58, 15, 13, 77, 51, 58};
    HeapSort(vec, vec.size());
    cout << "HeapSort: " << endl;
    for (auto &v : vec)
    {
        cout << v << endl;
    }

    return 0;
}