C / C++算法学习笔记（6）－插入法_插入法交换次数

原始地址：C / C++算法学习笔记（6）－插入法

 

插入法：

插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张。

 

#include <iostream.h>
 
void InsertSort(int* pData,int Count)
 
{
 
    int iTemp;
 
    int iPos;
 
    for(int i=1;i<Count;i++)
 
    {
 
        iTemp = pData[i];
 
        iPos = i-1;
 
        while((iPos>=0) && (iTemp<pData[iPos]))
 
        {
 
            pData[iPos+1] = pData[iPos];
 
            iPos--;
 
        }
 
        pData[iPos+1] = iTemp;
 
    }
 
}
 
 
 
 
 
void main()
 
{
 
    int data[] = {10,9,8,7,6,5,4};
 
    InsertSort(data,7);
 
    for (int i=0;i<7;i++)
 
        cout<<data[i]<<" ";
 
    cout<<"/n";
 
}
 

i=1时：

                      iTemp=pData[1]=9

                      ipos=1-1=0;

                      ipos=0>=0 && iTemp=9<pData[0]=10;

                      pData[1]=pData[0]=10;

                      ipos--=0-1=-1;

                      pData[0]=9;   9-10-8-7-6-5-4

i=2时：

                      iTemp=pData[2]=8

                      ipos=2-1=1;

                      ipos=1>=0 && iTemp=8<pData[1]=10;

                      pData[2]=pData[1]=10;