排序-插入排序(交换类型-循环嵌套)

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤：

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;
}