插入排序

插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。

算法步驟：

1. 將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。
2. 從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）

時間復雜度和空間復雜度

時間復雜度：
(1)最好： O(n）
（2)最壞：O(n2)
(3)平均： O(n2）

空間復雜度：
O（1）

參考代碼

C語言

#include <stdio.h>

void swap(int a[],int i ,int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

void sort(int a[],int length){
    for (int i = 1; i<length; i++) {
        for (int j = i; j>0; j--) {
            if (a[j] < a[j-1]) {
                swap(a, j, j-1);
            }else{
                break;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    // insert code here...
    int a[] = {1,6,4,8,7,5,3,2};
    sort(a,8);
    for (int i = 0; i<8; i++) {
        printf("%d ",a[i]);
    }
    return 0;
}