二分插入排序
二分插入排序
风中的树叶 发表于4年前
二分插入排序
  • 发表于 4年前
  • 阅读 1715
  • 收藏 5
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

    二分插入排序也称折半插入排序,基本思想是:设数列[0....n]分为两部分一部分是[0...i]为有序序列,另一部分是[i+1.....n]为无序序列,从无序序列中取一个数 x ,利用二分查找算法找到 x 在有序序列中的插入位置并插入,有序序列还是有序的,接下来重复上述步骤,直到无序序列全部插入有序序列 ,这是整个序列只剩下有序序列即有序了。

 

void  BinaryInsertSort(int *pArray, int len)
{
  //刚开始设有序序列只有一个元素 pArray[0],无序序列为[1...n]了
  for( int i = 1; i < len; i++)
  {
     //无序序列元素与有序序列比较(从有序列最后一个元素往前比较)
     if(pArray[i] >= pArray[i - 1])
     {
       continue;
     }
     //当无序序列元素比有序序列最后一个元素小时,利用二分查找法在有序序列中查找插入位置
     int low = 0; 
     int high = i - 1;
     int mid = 0;
     int temp = pArray[i];
     while(low <= high)
     {
       mid = (low + high) / 2;
       if(temp >= pArray[mid])
       {
          low = mid + 1;
       }
       else //(temp < pArray[mid])
       {
          high = mid - 1;
       }
     }
     //low位置就是要插入的位置,所以low到i之间的元素都需要往后移动一个位置
     int j = i;
     while(j > low)
     {
       pArray[j] = pArray[j - 1];
       j--;
     }
     //把无序序列中的pArray[i]放到有序序列中low的位置,这样就完成了无序序列 i 位置的数插入了有序序列中
     pArray[low] = temp;
  }

}
共有 人打赏支持
粉丝 2
博文 8
码字总数 2682
×
风中的树叶
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: