C++数据结构5 插入排序
插入排序和冒泡排序,选择排序并称三大低级排序,但是插入排序的速度是最快的。
插入排序就是默认第一个数是已经排序好的,从第二个开始拿出去记为temp,依次和已经排序好的数进行比较,如果temp比他们都大,则放在最右边,否则已经排序好的数依次移动,给temp一个适当的位置进行插入。
#include <iostream>
using namespace std;
template<class T>
void InsertSort(T *a,const int n) //a为数组,n为数组元素个数
{
int in,out;
//假设out=0;第一个数已经排序完成,先取出第二个数,在已经排序好的数进行比较
for(out=1;out<n;out++)
{
in=out;
T temp=a[out]; //拿出去一个数
while(in>0 & temp<a[in-1]) //如果拿出去的数比已经排序好的数小,则已经排序好的数向后移,直到遇到第一个(in=0)停止或者temp比这个数大为止
{
a[in]=a[in-1]; //向后移动数据
--in;
}
a[in]=temp; //结束循环把temp拿进去
}
}
int main()
{
double a[]={0,5,6,7,1,8,9,10,23,5,6.3,4.5};
InsertSort(a,sizeof(a)/sizeof(a[0]));
for(int i=0;i<(sizeof(a)/sizeof(a[0]));i++)
cout<<a[i]<<endl;
//cout << "Hello world!" << endl;
return 0;
}