排序算法之插入排序

前言

排序篇第三篇内容

排序原理

官话：

1、把所有元素分为两组，已排序和未排序

2、找到未排序的第一个元素，向已排序的组中进行插入操作

3、倒序遍历已经排序的元素，并进行比较，直到找到一个元素小于待插入元素（第一个满足此条件的元素），就把待插入元素放到这个位置

白话：

相当于起扑克牌，并没有进行排序，在你面前有一堆牌需要排序。拿起第一张，第二张进行比较，找到应该在的位置，以此类推完成整个数组的排序工作

时间复杂度分析

内部同样使用了双层循环，时间复杂度以大O记法记为：O(n^2)

C++实现

#include <iostream>
using namespace std;

int main()
{
    int sample[10] = { 2,4,1,3,23,5,7,0,11,14 };
    for (int i = 0; i < 10; i++) {
        int key = sample[i];
        int j = i - 1;
        while (j >= 0 && sample[j] > key) {
            sample[j + 1] = sample[j];
            j--;
            //实现插入之后目标位置后面所有元素的向后移动
        }
        sample[j + 1] = key;//实现交换数值
    }
    for (int i = 0; i < 10; i++)
        cout << sample[i] << endl;
}