插入排序（初级算法中速度最快的）

//插入排序

核心思想：先将一个数拿出去，然后在和里面的数值相比较。

#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;

}

}

插入排序步骤简化版（原创）