算法不会，尚能饭否之排序——折半插入排序（Binary Insert Sort）

以你之姓@ 2023-08-17 15:50 110阅读 0赞

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

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

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

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

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

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

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

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

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

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

转载于:https://www.cnblogs.com/JPAORM/archive/2011/03/14/2509903.html