波斯马BOSSMA Information Technology

折半插入排序，又称二分插入排序，实际上只是查找，是对插入排序算法的一种改进。
在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。?

static void BinaryInsertionSort(int[] intArr)
        {
            int numberOfLoop = 0;
            int numberOfSwap = 0;

            for (int i = 1; i < intArr.Length; i++)
            {
                //处理第i个数，i之前的数字排列是有序的
                int j;
                int temp = intArr[i];

                int low = 0;
                int high = i - 1;
                while (low <= high)
                {
                    numberOfLoop++;

                    //有序部分的的中间位置
                    int middle = (low + high) / 2;
                    if (intArr[middle] > temp)
                    {
                        high = middle - 1;
                    }
                    else
                    {
                        //最后low就是大于temp的第一个数的前一个位置
                        low = middle + 1;
                    }
                }

                //找到插入的位置了：low
                for (j = i - 1; j >= low; j--)
                {
                    numberOfLoop++;
                    numberOfSwap++;
                    intArr[j + 1] = intArr[j];
                }

                //最后一个位置设置成要排序数
                numberOfSwap++;
                intArr[low] = temp;
            }

            DisplaySortResult(numberOfLoop, numberOfSwap, intArr);

        }

其运行效率要比直接插入排序和希尔排序都要好：

关键字: 二分插入排序 折半排序 排序算法