一个好脑袋比不过一杆破笔头。插入排序，读完严蔚敏老师的教材，根据自己的理解写的。木有看严蔚敏老师的代码实现。正所谓，看别人的算法代码，比自己写起来要难的多。特此声明，代码是根据自己对插入排序的理解实现的，不一定正确，如有问题，可留言告知，3Q。
/*
* 插入排序，严蔚敏老师教材读后感。
* 1：生成一个已完成排序的数组。
* 2：将待排序的数据插入到已完成排序的数组中，并保证已完成排序的数组仍旧是已排序。
* 思路可以参考函数 xf_InsertSortIncrease_YWM 的实现。
*/
#include <iostream>
using namespace std;
void xf_Swap(int& x,int& y)
{
int temp = x;
x = y;
y = temp;
}
/*
* 严蔚敏老师的思路，先构建一个已经排序的数组，然后将待排序的元素插入到已排序数组的正确位置，保证加入新元素的数组仍旧满足已排序。
*/
void xf_InsertSortIncrease_YWM(int ary[],int aryLen)
{
//已排序的数组最后一个元素的下标
int lastElementIndexOfSortAry = 1;
//构建一个以数组下标为0，1的元素组成的已排序数组
if( ary[0]>ary[lastElementIndexOfSortAry])
{
xf_Swap(ary[0],ary[lastElementIndexOfSortAry]);
}
//开始插入排序i，就是将已排序数组ary[0,1]之后的元素插入到ary[0,1]中来，保证ary[0,1,2]仍旧为已排序。直到ary[0,1...9,10]为已排序。
for( int i=lastElementIndexOfSortAry+1;i<aryLen;++i)
{
//将i与已排序数组中的元素比较，从后往前比较
int indexCurrentOper = i;
for( int j=lastElementIndexOfSortAry;j>=0;--j)
{
if(ary[indexCurrentOper] < ary[j])
{
xf_Swap(ary[indexCurrentOper],ary[j]);
indexCurrentOper = j;
}
}
lastElementIndexOfSortAry = i;
}
}
void xf_InsertSortIncrease(int ary[],int aryLen)
{
//已排序的数组最后一个元素的下标,默认用数组第一个元素初始化为已排序的数组。即已排序的数组初始化时只有一个元素。
int lastElementIndexOfSortAry = 0;
//开始插入排序i
for( int i=lastElementIndexOfSortAry+1;i<aryLen;++i)
{
//将i与已排序数组中的元素比较，从后往前比较
int indexCurrentOper = i;
for( int j=lastElementIndexOfSortAry;j>=0;--j)
{
if(ary[indexCurrentOper] < ary[j])
{
xf_Swap(ary[indexCurrentOper],ary[j]);
indexCurrentOper = j;
}
}
lastElementIndexOfSortAry = i;
}
}
void xf_InsertSortDecrease(int ary[],int aryLen)
{
//已排序的数组最后一个元素的下标,默认用数组第一个元素初始化为已排序的数组。即已排序的数组初始化时只有一个元素。
int lastElementIndexOfSortAry = 0;
//开始插入排序i
for( int i=lastElementIndexOfSortAry+1;i<aryLen;++i)
{
//将i与已排序数组中的元素比较，从后往前比较
int indexCurrentOper = i;
for( int j=lastElementIndexOfSortAry;j>=0;--j)
{
if(ary[indexCurrentOper] > ary[j])
{
xf_Swap(ary[indexCurrentOper],ary[j]);
indexCurrentOper = j;
}
}
lastElementIndexOfSortAry = i;
}
}
int main(int argc,char** argv)
{
int ary[10] = {38,49,65,97,44,27,18,66,55,99};
cout << "befor insert sort ,array number is:" << endl;
for(int i=0;i<10;++i)
{
cout << ary[i] << endl;
}
//xf_InsertSortIncrease(ary,10);
xf_InsertSortDecrease(ary,10);
cout << "after insert sort ,array number is:" << endl;
for( int i=0;i<10;++i)
{
cout << ary[i] << endl;
}
return 0;
}