排序演算法 2

今天來介紹選擇排序法跟合併排序法

選擇排序法

選擇排序法是先從未排序的陣列中選最小的，然後跟第一個元素做交換，接著從剩餘的元素做一樣的事，直到最後一個元素，執行效率是O(n ^ 2)

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

using namespace std;

template <typename T>
void SelectionSort(vector<T> &vec)
{
    int index = 0;
    // 使用stl迭代器找小元素的函式
    auto minIter = min_element(vec.begin(), vec.end());

    while (index < vec.size())
    {
        // 找迭代器實際的index
        int minIndex = distance(vec.begin(), minIter);
        if (minIndex != index)
        {
            swap(vec[index], *minIter);            
        }
        
        index++;
        minIter = min_element(vec.begin() + index, vec.end());
    }    
}

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

合併排序法

合併排序法是會將陣列對半分，直到分到單個元素，再從單個元素倆倆合併排序回去，執行效率是O(n log n)

template <typename T>
void Merge(vector<T> &vec, int left, int right, int mid)
{
    int nLeft = mid - left + 1;
    int nRight = right - mid;

    vector<T> vecLeft(nLeft);
    vector<T> vecRight(nRight);

    for (int i = 0; i < nLeft; i++)
    {
        vecLeft[i] = vec[left + i];
    }

    for (int i = 0; i < nRight; i++)
    {
        vecRight[i] = vec[mid + 1 + i];
    }

    int i = 0, j = 0, k = left;
    while (i < nLeft || j < nRight)
    {
        if (i >= nLeft)
        {
            vec[k++] = vecRight[j++];
            continue;
        }

        if (j >= nRight)
        {
            vec[k++] = vecLeft[i++];
            continue;
        }
        
        if (vecLeft[i] < vecRight[j])
        {
            vec[k++] = vecLeft[i++];
        }
        else
        {
            vec[k++] = vecRight[j++];
        }
    }
}

template <typename T>
void MergeSort(vector<T> &vec, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        MergeSort(vec, left, mid);
        MergeSort(vec, mid + 1, right);
        Merge(vec, left, right, mid);
    }
}

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