十大排序算法之——插入排序算法

插入排序，故名思緒，找一個合适的數，插入到相應的位置來達到集合整體有序的目的，具體來說以遞增排序為例。取無序集合的首元素，從有序集合的末尾開始找，直到找到一個小于該元素的值結束周遊，将無序集合的元素插入到找到這個元素的後面。

因為不會改變兩個相等元素的位置，是以是穩定排序，隻需要一個額外的空間，是以控件複雜度為O(1)，時間複雜度為O(n^2)。

例如，有集合1,2,7,9,6,3。1,2,7,9部分就是有序的，6,3部分就是無序的，無序集合的首元素就是6，那麼問題就是6該插入到什麼位置，從有序集合的1,2,7,9末尾9開始找，設6的下标為x,9的下标為y,6<9，那麼y--，将9元素向後移一位，空出位置将來放“6”;6<7，y--，7元素後移一位；6>2，此時周遊結束，因為y此時是1，是以放6的位置應該是y+1；然後不斷的循環下去。

#include<string>
#include<iostream>
#include<cstring>
#include<head.h>
using namespace std;
//插入排序算法，選出無序集合的第一個元素，從有序集合的末尾開始掃描，直到第一個大于該數，插入到其後面
void insertSort(int *,int);
int main()
{
    int arr[] = {7,1,6,4,5,2,8,10,3,9,11,12};
    int length = sizeof(arr)/sizeof(int);
    cout << "原來的序列：" << endl;
    for(auto var : arr)
    {
        cout << var << " ";
    }
    insertSort(arr,length);

    cout << "\n現在的序列：" << endl;
    for(auto var : arr)
    {
        cout << var << " ";
    }

    return 0;
}

void insertSort(int *arr,int length)
{
    for(int ix=1;ix<length;++ix)
    {
        int curr_elem = arr[ix];    //1     //ix是無序集合，是以需要取無序集合的首元素和有序集合的jy進行對比
        int jy = ix - 1;            //0
        while(jy>=0 && curr_elem < arr[jy])
        {
            arr[jy + 1] = arr[jy];
            jy--;
        }
        arr[jy + 1] = curr_elem;
    }
}
           

輸出：

原來的序列：
7 1 6 4 5 2 8 10 3 9 11 12
現在的序列：
1 2 3 4 5 6 7 8 9 10 11 12
           

注意1：記憶體循環jy跳出循環的條件是jy>=0，我不是jy>0,因為還需要和第一個元素進行比較。

注意2：因為元素需要不斷向後移，是以無需集合的首元素，一定要copy一份，避免被覆寫。