插入排序讲解

插入排序（Insertion-Sort）一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动，从而实行排序的目的。

插入排序图示：

 来看看插入排序的模板题：

因为前面讲过插入排序的思想，所以具体的看代码：

void insertion_sort(int a[],int n){for(int i = 2; i <= n; i++){int j = i-1;//不能用i，因为后面要j--的int key = a[i];//定义key等于当前要比的数while(j >= 1 && a[j] > key){a[j+1] = a[j];j--;}//然后循环，j >= 1是保证不越界，a[j] > key是当a[j]大于key的时候才循环，如果a[j]小于key了，就把key插在这里了a[j+1] = key;//插入key}
}

CODE：

#include <bits/stdc++.h>
using namespace std;
int a[1001];
void insertion_sort(int a[], int n){for(int i = 2; i <= n; i++){int key = a[i];int j = i-1;while(j >= 1 && a[j] > key){a[j+1] = a[j];j--;}a[j+1] = key;}
}
int main(){int n;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];insertion_sort(a,n);for(int i = 1; i <= n; i++) cout << a[i]<<" ";return 0;
}