算法原理：将待排序的数组分为：有序区 和 无序区。然后每次从无序区取出第一个数据插入到有序区的正确位置，最终完成排序。
算法代码：
#include <iostream> using namespace std; void insert_sort(int *arr,int n) { int i,j; for(i = 1 ; i < n ; ++i) { int tmp = arr[i]; j = i - 1; while( j >= 0 && arr[j] > tmp) { arr[j+1] = arr[j]; j--; } arr[j+1] = tmp; } } int main() { int arr[] = {2,4,1,3,5,8,7,6,8}; insert_sort(arr,9); for(int i = 0 ; i < 9 ; ++i) { cout<<arr[i]<<" "; } cout<<endl; return 0; }
小结：看代码可以知道这种排序算 法的时间复杂度是O(n^2)，并且插入排序时稳定的，属于原地排序。那么什么时候使用插入排序比较好呢？那就是当数组中的大部分数据已经有序时，使用插 入排序算法的效率比较高，这种情况下，所需要进行的数据移动较少，而数据移动正式插入排序算法的主要步骤~~~~