二分法排序C++

全栈程序员-站长 • 2026年3月18日下午12:32 • 未分类 • 阅读 2

首先说一下二分法排序的原理，算法思想简单描述：
在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们
中间的那个元素比，如果小，则对前半再进行折半，否则对后半
进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间
的所有元素后移，再把第i个元素放在目标位置上。

二分法排序最重要的一个步骤就是查找要插入元素的位置，也就是要在哪一个位置上放我们要准备排序的这个元素。
当我们查找到位置以后就很好说了，和插入排序一样，将这个位置以后的所有元素都向后移动一位。这样就实现了二分法排序。
　　然后是怎么查找着一个位置呢，就是不断的比较已排序的序列中的中间元素和要排序元素，如果大于的话，说明这个要排序的元素在已排序序列中点之前的序列。

#include

#include

void TwoInsertSort(int array[],int n)
{

int left,right,num;
int middle,j,i;
for(i = 1;i < n;i++)
{

left = 0;// 准备
right = i-1;
num = array[i];
while( right >= left)// 二分法查找插入位置
{

middle = ( left + right ) / 2; //　指向已排序好的中间位置
if( num < array[middle] )// 即将插入的元素应当在在左区间

right = middle-1;

else //　即将插入的元素应当在右区间

left = middle+1;

}

//每次查找完毕后，left总比right大一，a[left]总是存放第一个比num大的数，因此应从此处开始，每            //个元素右移一位，并将num存入a[left]中，这样就保证了a[0…i]是排好序的
          for( j = i-1;j >= left;j– )//　后移排序码大于R[i]的记录
              array[j+1] = array[j];
          array[left] = num;// 插入
      }
}

看了以后就会发现，其实就是插入排序法的一种修改，当a[0],a[1]…a[i-1]排好序，寻找第i个元素在其中的位置时采用二分查找法，于是该算法称二分排序法，所以我认为这不是新的算法；另外有人说起时间复杂度是n*lgn的，其实不是，就算每次查找的时间是lgi,但是查找完毕还要移动元素，这个时间平均为i/2,于是总时间为(1/2+lg1) + (2/2 + lg2) + (3/2 + lg3) + … + ((n-1)/2 + lg(n-1)), 约为n(n-2)/4+nlgn，所以时间复杂度还是n*n的。