波斯马BOSSMA Information Technology

c#排序算法之折半插入排序

发布时间:2010年9月14日 / 分类:DOTNET / 7,911 次浏览 / 评论

折半插入排序,又称二分插入排序,实际上只是查找,是对插入排序算法的一种改进。
在插入第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);

        }

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

本博客所有文章如无特别注明均为原创。
复制或转载请以超链接形式注明转自波斯马,原文地址《c#排序算法之折半插入排序

关键字:

建议订阅本站,及时阅读最新文章!
【上一篇】 【下一篇】

发表评论