//插入排序
核心思想：先将一个数拿出去，然后在和里面的数值相比较。
#include <iostream>
using namespace std;
template <class T> //函数模板，不需考虑数据类型
void InsertionSort(T *a,int n);
int main(){
int x[]={3,2,1,4,5,8,0,3,1};
double a[]={3.0, 2,1, 4.5, 5,8,0,3,1};
InsertionSort(x,9);
for(int i=0;i<9;++i){
cout<<x[i]<<endl;
}
return 0;
}
template <class T>
//函数模板，不需考虑数据类型
void InsertionSort(T *a,int n){
int in,out;
//out=0这个数出去
for(out=1;out<n;++out){
int t=a[out];//注意这里
in=out;
while(in>0&&a[in-1]>=t) {
a[in]=a[in-1];
--in;
}
a[in]=t;
}
}
//改进算法//浪费了一个空间
void InsertionSort_2(int *a,int n){
//a[0]用来保存排序使用，不能保存原始数据
for(int j=2;j<=n;++j){
int temp=a[j];
a[0]=temp;
int i=j-1;
while(temp<a[i]){
a[i+1]=a[i];
i--;
}
a[i+1]=temp;
}
}
插入排序步骤简化版（原创）
