排序演算法 1

今天來介紹氣泡排序法跟插入排序法，分別是兩個比較基礎好用的排序法

氣泡排序法

氣泡排序法原理是將兩個相鄰的數值做比較，若前面一個數值比後面的大就做對調，然後針對陣列每個元素，所以執行次數是 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1)/2 ，實際上執行效率是O(n^2)，n是陣列長度，n - 1代表第一個數跟後面每個數比較的次數

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

using namespace std;

template <typename T> 
void BubbleSort(vector<T> &vec)
{
    for (size_t i = 0; i < vec.size(); i++)
    {
        for (size_t j = i+1; j < vec.size(); j++)
        {
            if (vec[i] > vec[j])
            {
                swap(vec[i], vec[j]);
            }            
        }        
    }    
}

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

插入排序法

插入排序法是針對有序的陣列，對於沒排序的數據加入，會從已排序的陣列中由後往前比對出相應的位置插入，執行效率最差的情況是每筆數值需要跟陣列中其他數值比較，所以會是O(n^2)

template <typename T>
void InsertSort(vector<T> &vec, bool useBinary = true)
{
    // 預設第一筆是排序的
    int index = 0;
    for (size_t i = 1; i < vec.size(); i++)
    {        
        if (useBinary)
        {
            // 使用二分法
            int left = 0;
            int right = index;
            while (left <= right)
            {
                auto mid = (left + right) / 2;
                if (vec[i] < vec[mid])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            T value = vec[i];
            vec.erase(vec.begin() + i);
            vec.insert(vec.begin() + left, value);
        }
        else
        {
            // 直接逐個比較
            int tmp = index;
            bool isFirst = false;
            while (tmp >= 0)
            {
                if (vec[i] < vec[tmp])
                {
                    int value = vec[i];
                    vec.erase(vec.begin() + i);
                    vec.insert(vec.begin() + i, value);

                    isFirst = true;
                    break;
                }

                tmp--;
            }

            if (isFirst)
            {
                int value = vec[i];
                vec.erase(vec.begin() + i);
                vec.insert(vec.begin(), value);
            }            
        }
 
        index++;
    }
}

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