C++插入排序算法实例
插入排序
没事喜欢看看数据结构和算法，增加自己对数据结构和算法的认识，同时也增加自己的编程基本功。插入排序是排序中比较常见的一种，理解起来非常简单。现在比如有以下数据需要进行排序：
10380692
当使用插入排序进行升序排序时，排序的步骤是这样的：
10380692//取元素3，去和10进行对比
31080692//由于10比3大，将10向后移动，将3放置在原来10的位置；再取8与前一个元素10进行对比
38100692//同理移动10；然后8再和3比，8大于3，所以不再移动；如此重复下去
……
02368910
也就是说，我们每一次取一个元素，都要将该元素与之前已经排序好的元素进行比较。
插入排序的最差时间复杂度为O(n^2)。同时，该算法不需要开辟额外的空间，都是在原空间上进行移动操作。
代码实现
#include<iostream>
usingnamespacestd;
voidInsertSort(intarr[],intlength)
{
inttemp;
for(inti=1;i<length;++i)//从数组中的第二个元素开始
{
temp=arr[i];//记录当前的元素
intj=i-1;
while(j>=0&&temp<arr[j])//将当前元素与之前的已经排序好的序列元素进行挨个比较
{
arr[j+1]=arr[j];//已经排序好的序列整体向后移动
--j;
}
arr[j+1]=temp;//插入当前的元素
}
}
intmain()
{
intarr[10]={9,2,8,2,3,2,4,10,34,5};
InsertSort(arr,10);
for(inti=0;i<10;++i)
{
cout<<arr[i]<<"";
}
cout<<endl;
return0;
}