【C++】插入排序基本實作和性能調優

參考：https://blog.csdn.net/pilipilipan/article/details/79702298

簡述

插入排序跟選擇排序很像，都分為有序區和無序區。但是選擇排序是每次都從無序區中選出最小元素插入到有序區末尾，而插入排序是直接将數組的第一個元素作為有序區的第一個元素，每次都拿出無序區第個一進制素插入到有序區合适的位置上，直到無序區為空，排序完成。

算法描述

1 将數組分為有序區和無序區，有序區0,無序區[1,n-1]；

2 取下無序區第一個元素，儲存其值。

3有序區中元素從後往前與新元素比較，如果新元素更小，舊元素往後移。

3 重複步驟3，直到新元素大于或等于舊元素，将新元素插入該元素之後。

4 重複步驟234， n-1次，排序完成。

算法分析

最好：T(n)=o(n)，數組元素正序排列

最壞：T(n)=o(n^2)數組元素反序排列

平均：T(n)=o(n^2)

代碼實作：

#include<iostream>
#include<vector>

using namespace std;

void insertSort(vector<int>& a) {
    for (int i = 1;i < a.size();++i) {
        int j = i - 1;//j初始化為有序區最後一個數，也是無序區的前一個數
        int val = a[i];//要插入到前面有序區的數，備份
        while (j >= 0 && a[j] > val) {//有插入必要
            a[j + 1] = a[j];//有序區數字後移，給新數騰位置
            --j;
        }
        a[j + 1] = val;//騰出的合适的位置就是j+1對應的位置
    }
}

//列印數組
void printVector(const vector<int>& a) {
    for (auto i : a) {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
    vector<int> a{ 5,6,4,2,3 };
    insertSort(a);
    printVector(a);
    return 0;
}
           

算法優化-使用二分法找到最優插入點

#include<iostream>
#include<vector>

using namespace std;

//基本實作
void insertSort(vector<int>& a) {
    for (int i = 1;i < a.size();++i) {
        int j = i - 1;//j初始化為有序區最後一個數，也是無序區的前一個數
        int val = a[i];//要插入到前面有序區的數，備份
        while (j >= 0 && a[j] > val) {//有插入必要
            a[j + 1] = a[j];//有序區數字後移，給新數騰位置
            --j;
        }
        a[j + 1] = val;//騰出的合适的位置就是j+1對應的位置
    }
}

//算法優化-使用二分法找到最優插入點
void insertSort1(vector<int> &a) {
    int len = a.size();
    for (int i = 1; i < len; ++i) {
        int key = a[i];

        int left = 0, right = i - 1;
        while (left <= right) {//在區間内查找位置
            int middle = (left + right) / 2;
            if (a[middle] > key)
                right = middle - 1;
            else left = middle + 1;
        }
        for (int j = i - 1; j >= left; --j) {
            a[j + 1] = a[j];
        }

        a[left] = key;//left為新元素要插入的位置
    }
}

//列印數組
void printVector(const vector<int>& a) {
    for (auto i : a) {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
    vector<int> a{ 5,6,4,2,3 };
    insertSort1(a);
    printVector(a);
    return 0;
}