注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ksnowlv的博客

积土成丘,集腋成裘,坚持再坚持!

 
 
 

日志

 
 

二分插入排序  

2013-09-03 21:23:24|  分类: 算法与数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
// BinarySortTest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;

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

    for(int i = 1;i < n;i++)
    {
        int left = 0;
        int right = i-1;
        int num = array[i];

        while( right >= left)
        {
            int middle = ( left + right ) / 2; // 指向已排序好的中间位置
            if( num < array[middle] )// 即将插入的元素应当在在左区间
                right = middle-1;
            else                    // 即将插入的元素应当在右区间
                left = middle+1;    
        }
        /*每次查找完毕后,索引left对应值是第一个比num大的数,因此应从此处开始,每            
            个元素右移一位,并将num存入a[left]中,这样就保证了a[0...i]是排好序的
            */
        for( int j = i-1;j >= left;j-- )
            array[j+1] = array[j];
        array[left] = num;// 插入
    }
}


int _tmain(int argc, _TCHAR* argv[])
{
    const int KLength = 10;
    int array[KLength] = {13,45,21,17,19,56,98,1,5,34};

    BinaryInsertSort(array,KLength);

    for (int i =0; i < 10; ++i)
    {
        cout<<array[i]<<"->";
    }

    cout<<endl;
    return 0;
}

日志输出如下:
1->5->13->17->19->21->34->45->56->98->
请按任意键继续. . .
  评论这张
 
阅读(52)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018