C++、C#、java算法学习日记04二分插入排序

经过上几篇对排序算法的了解,我们发现,所谓的排序也就是确定一个数组中每个元素的位置,然后对号入座,其过程也就是找到该元素的位置。确定位置,使用二分法可以达到很高的效率,我们将他应用到插入排序中就算是对上篇中排序的一种优化,能提高效率。

基本思想:

与上篇中的插入排序类似分已排序和未排序部分,然后将未排序 部分元素逐个插入,但是插入的过程不同,需要每次求一个 中间位置,和中间位置元素比较大小,然后根据大小情况,将高位 左移或者将低位右移,再求中间元素比较,直到找到合适位置 (也就是说使用二分法确定插入位置)后 将其部分元素后移为待插入元素腾出空间,再插入该序列即可。

C++实例:

#include

using namespace std;

void HalfSort(int *array,int Length)
{//定义最低,最高,中间值,待插入数据,插入位置
	int low,high,middle,temp,index,i,j;
	for(i=1;itemp) //与头尾相比较如果没在范围类省略循环
	  {
	    while(low<=high) //二分法查找插入位置
		{
		  middle=(low+high)/2;
		  if(array[middle]>temp)
		  {
		    high=middle-1;
		  }
		  else
			  low=middle+1;
		}
		//最后确定位置index
		index=low;
	  }
	  if(array[0]>=temp) //如果比第一个元素还小就直接插到第一个位置
	  { index=0;}
	  if(array[i-1]<=temp) //如果比最后一个元素还大直接插到最后一个位置
	  { index=i;}
	  //向后移位腾出插入空间
	  for(j=i-1;j>=index;j--)
	  { array[j+1]=array[j];}
	  array[index]=temp; //插入
	}
	//输出
	for(i=0;i

 

C#实例:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HalfSort2
{
    class Sort
    {
        public void halfSort(int[] array)
        {
          int low,high,middle,temp,index,i;
          for (i = 1; i < array.Length; i++)
          {
              low = 0;
              high = i - 1;
              temp = array[i];
              index = i;
              if (array[0] < temp && array[i - 1] > temp)
              {
                  while (low <= high) //二分法查找插入位置
                  {
                      middle = (low + high) / 2;
                      if (array[middle] > temp)
                      {
                          high = middle - 1;
                      }
                      else
                          low = middle + 1;
                  }
                  index = low;
              }
              if (array[0] >= temp) //如果比第一个元素还小就直接插到第一个位置
              { index = 0; }
              if (array[i - 1] <= temp) //如果比最后一个元素还大直接插到最后一个位置
              { index = i; }
              //向后移位腾出插入空间
              for (int j = i - 1; j >= index; j--)
              { array[j + 1] = array[j]; }
              array[index] = temp; //插入
          }
          foreach (int j in array)
          {
              Console.Write(j +   );
          }
          Console.WriteLine();
        }
        static void Main(string[] args)
        {
            int[] array = new int[] {63,4,24,1,3,15};
            Sort sorter = new Sort();
            sorter.halfSort(array);
        }
    }
}


以上结果为:

C++、C#、java算法学习日记04二分插入排序

java实例:

package Sort;

public class Sort {
public void halfsort(int[] array){
	int low,high,middle,temp,index,i;
	for(i=1;itemp){
        	 while(low<=high){
        		 middle=(low+high)/2;
        		 if(array[middle]>temp){
        			 high=middle-1;
        		 }
        		 else{
        			 low=middle+1;
        		 }
        	 }
        	 index=low;
         }
         if(array[0]>=temp){
        	 index=0;
         }
         if(array[i-1]<=temp){
        	 index=i;
         }
         for(int j =i-1;j>=index;j--){
        	 array[j+1]=array[j];
         }
         array[index]=temp;
	}
	for(int j:array){
        	 System.out.print(j+  );
         }
}
	public static void main(String[] args) {
		int[] array = new int[]{63,4,24,1,3,15};
		Sort sorter = new Sort();
		sorter.halfsort(array);
		
	}

}


结果:

C++、C#、java算法学习日记04二分插入排序

 

 

其实关于二分法排序,我查阅资料的时候代码中并没有 if(array[0]temp) ,if(array[0]>=temp),if(array[i-1]<=temp) 这样的判断语句,这是我自己加上的,因为如果没有这些判断语句的话,当让你排序的数列已经是有序数列的时候程序还是会经历一些不必要的循环,反倒不如上一篇中的直接插入排序了。

 

 

更多相关文章
  • Internet安全: 防火墙及其他  TCP/IP协议群在网际互联中的使用的迅速崛起 导致了通常被称为Internet的  由主机和网络组成的全球网际互联系统.过去的十年 是Internet胜利大进军  的十年.按它现在的发展速率预测 到本世纪末 将有超过一百万个计算机网  络和超过十亿的用户加入 ...
  • 数据结构与算法是大多前端程序员的短板,传统的前端开发都是在跟浏览器兼容作斗争很少会涉及到复杂的结构设计 本系列参考了数据结构与算法JavaScript描述.大话数据结构.数据结构与算法分析,网上的资料等等 通过分析总结其它语言的实现从而转化成javascript版,主要是为了学习 附上每一章的源码注 ...
  • 本文首发于烂泥行天下. 上篇文章我们介绍了如何使用rsync同步文件,这篇文章我们再来介绍下,如何把rsync与inotify集成实现数据的实时同步. 要达到这个目的,我们需要分以下几个步骤: 1.rsync的优点与不足 2.inotify是什么 3.检测OS是否支持inotify 4.inotif ...
  • 本站已经报道过这个时间好几次了,大家可以查一下以前的报道: 网上支付是否安全?数字证书是否安全?出事后倒霉的只能是用户自己吗? 基本案情 涉及金额16余万元,上海发生过的最大的网络盗窃案---"3·10"特大盗窃案日前告破.在上海市警方缜密侦查和云南警方的大力协助下,犯罪嫌疑人白 ...
  • 默认脚本只开启常规web服务器的80,3306,22端口   #vi default_firewall.sh   #!/bin/bash ######################################################################### # # Fil ...
  • 1,HTML的Form表单数据按Button提交数据以后,由 Action 指定的服务器端处理程序(.ashx)进行处理后 ,再响应的浏览器. 2,我们把 HTML的表单,写到 .ashx 一般处理程序页面中,这样就一般处理程序页面就可以显示 Form表单登陆,并且可以处理是否登陆成功的逻辑部分, ...
一周排行
  • 众所周知,Oracle有很多坑, 所以才有了去IOE. 在使用Druid做数据库连接池后,其实偶尔也会碰到小坑,这就是使用开源项目所必须去填平的. 用Druid连接池,通过JDBC往Oracle数据库的Clob字段插 ...
  • 动态代码布局 如何添加代码布局 代码布局注意的问题 代码布局和XML布局的性能比较 如何添加代码布局 for example -- 简单布局LinearLayout LinearLayout llayout = ne ...
  • pog loves szh III    Accepts: 63    Submissions: 483  Time Limit: 12000/6000 MS (Java/Others)    Memory Limi ...
  • 如何使用C#的事件来监控变量的改变?这是一个非常常见的问题.并且如果能够使用事件来解决的话对于编程会带来很大的便利同时保持性能的优良.   以下是完整的代码 01 public class Program 02 { ...
  • 前面花了两节内容分别在<CSS3选择器--基本选择器>和<CSS3选择器--属性选择器>介绍了CSS3选择器中的基本选择器和属性选择器使用方法,今天要和大家一起学习CSS3选择器中的第三部分, ...
  • Internet,互联网络的现状,就如我们的交通,会出现拥堵,迟缓的现象.那么,很多访问用户,很多的网络使用者的同时运作就会出现流量分配等数据分配不均匀的情况.那么,一个有效的管理和操作理念——负载均衡,就是我们改善 ...
  • 在使用关系数据库时,我们通过sql语句来检索数据源,这没有任何问题,但是关系数据也存在着一定的局限性,只能存储结构化的数据 当数据集是非结构化的时候该怎样存储呢,最简单的办法就是封装成xml. 应用开发中我们经常使用 ...
  • 最近一个网友发来一个叫<3D角斗士>的游戏,让我帮着解绑. 我试了一下,用0.1版的c8解绑机确实无法解绑.这是因为假程序启动后没有立刻恢复真游戏程序,而是过了7,8秒才恢复真游戏程序. 0.1版的c8解 ...
  • 本文作者:sodme本文出处:http://blog.csdn.net/sodme声明: 本文可以不经作者同意, 任意, 转载, 但任何对本文的引用都请保留文章开始前三行的作者, 出处以及声明信息. 谢谢.前记:这是 ...
  • 提到mysql,我顺便讲讲序列.用过oracle的人都知道,orale没有类似mysql的AUTO_INCREMENT这样的自增长字段,实现插入一条记录,自动增加1.oracle是通过sequence(序列)来完成的 ...