学步园

    还是排序，上一篇讲的是排序大家庭中的直接插入排序，今天呢，主要讲的是折半插入排

序。实现起来，还是蛮简单的，没有太多的拐弯抹角的，不会伤害很多脑细胞的。人家都

说了，编程，如何提高自己的编程技术呢？那就是多写代码，如何写呢？就是抛开课本，拿着

笔和纸，现在纸上走一遍算法（这个前提是算法思想已经熟透了），然后，在写出来，编译，

运行。就是这样。很简单的。其实，在写这些简单的算法的时候，没有太多的技术问题，就是

一个如何提高自己的编程水平的问题，一种整体把握的能力。你能一次就把折半插入排序写

好，编译，运行通过吗？还好！我做到了（这里牛皮不是吹的！）。

   算法思想：在顺序表中，v[0], v[1], v[2],……v[n - 1], v[n]，而前n个数是已经排好的，现

在你的任务就是用折半排序将v[n]插入到已经排好的序列中。现在开始，定位。iLeft表示最左

边元素的位置，iRight表示最右边元素的位置，看好了，是位置，而不是值。iLeft = 0;

iRight = n – 1; 现在开始是定位中间位置的时候，iMiddle = (iLeft + iRight) / 2;如果v[n]比

v[iMiddle]大的话，就将iLeft = iMiddle + 1;否则，iRight  = iMiddle – 1;然后就是循环上面

的动作，就此，一个全新的折半插入排序就诞生了。

贴出代码：

注：本程序在visual studio 2008下编译通过，如有错误，请使用visual studio 2008.谢谢合作。

#include <iostream><br /> #include <stdlib.h></p> <p>using namespace std;</p> <p>void BinInsertSort(); //折半排序</p> <p>void main()<br /> {<br /> BinInsertSort();<br /> }</p> <p>void BinInsertSort()<br /> {<br /> int iNum; //参加排序的数的个数<br /> cout<<"请输入参加排序数个数:";<br /> cin>>iNum;</p> <p> //判断num的有效性<br /> if (iNum <= 0)<br /> {<br /> cout<<"请输入正确的个数"<<endl;</p> <p> exit(0);<br /> }</p> <p> int *Array = new int[iNum]; //动态开辟数组存放排序的数</p> <p> for (int i = 0; i < iNum; i++)<br /> {<br /> cin>>Array[i];</p> <p> int iLeft, iRight, iMiddle;<br /> int iTemp;<br /> int j; //数组循环变量</p> <p> iLeft = 0;<br /> iRight = i;<br /> iTemp = Array[i]; //存放新输入的数组值，防止被覆盖</p> <p> //折半排序<br /> while (iLeft <= iRight)<br /> {<br /> iMiddle = (iLeft + iRight) / 2; //获得中间位置</p> <p> //如果输入的数大于中间数，则向右走，否则向左走<br /> if (Array[i] > Array[iMiddle])<br /> {<br /> iLeft = iMiddle + 1;<br /> }<br /> else<br /> {<br /> iRight = iMiddle - 1;<br /> }<br /> }</p> <p> //移动数组值，将新值插入<br /> for (j = i; j > iLeft; j--)<br /> {<br /> Array[j] = Array[j - 1];<br /> }</p> <p> Array[j] = iTemp;<br /> }</p> <p> //输出排序结果<br /> for (int m = 0; m < iNum; m++)<br /> {<br /> cout<<Array[m]<<",";<br /> }<br /> cout<<endl;<br /> }<br />

好了，就写到这里了，如果对代码还有什么疑问，请跟帖提出，或者直接加我QQ：535064959.你我互相学习，共同提高，谢谢合作！

    现在可以享受自己的成果的时候了。