插入排序的步骤如下：
1. 设定待排列数组的第一位为已知有序序列，指针指向第一位。
2. 若数组长度大于1，则指针从指向第二位开始，将指针向后移动一位，每次移动之前，将指针所指位置与指针所指位置之前的有序数列进行比对，经过若干次交换后获得新的有序数列。重复本步骤直至整个数组为有序数列。
代码如下：
头文件Sort.h
//自己编写的各种排序算法的头文件。//使用静态类型的函数是为了在调用时候不需要实例化，直接通过类名调用。#ifndef _SORT_H#define _SORT_H//冒泡排序class bubble_sort{private: int *Array,Length;public: bubble_sort(int *Array1,int Length); int *sort_bubble();};//归并排序class merge_sort{public: static void sort_merge(int Array1[], int Array2[], int Left, int Rightend, int Right,int recursion/*递归flag*/); static void Merge(int Array1[], int Array2[], int Left, int Rightend);//递归方法 static void Merge_pass(int Array1[], int Array2[], int ordered_len,int Length); static void Merge1(int Array1[], int Array2[], int Length);//非递归方法};class quick_sort{public: static void sort_quick(int Array1[],int Left,int right); };//插入排序class insertion_sort{public: static void sort_insertion(int Array[],int n);};#endif insertion_sort.cpp
#include "Sort.h"void insertion_sort::sort_insertion(int Array[],int n){ if (n > 1) { for (int i = 1; i < n; i++) { int point = i; for (int j = point - 1; j >= 0; j--,point--) { if (Array[j] <= Array[point]) break; else { int temp = Array[j]; Array[j] = Array[point]; Array[point] = temp; } } } }} main.cpp
#include#include "Sort.h"using namespace std;void main(){ int Array[] = { 3, 2, 5, 7, 6, 2, 8, 10, 22, 434, 66 }; int Array1[] = { 1 }; int Array2[] = { 5, 4, 3, 2, 1 }; int n = sizeof(Array2) / sizeof(int); insertion_sort::sort_insertion(Array2, n); for (int i = 0; i < n;i++) cout << Array2[i] << endl; system("pause");}
总结一下：
插入排序的时间复杂度是O（n^2）。是比较简单的一种排序，作者也是现学现用，若有不足之处欢迎指出。