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表单登陆,并且可以处理是否登陆成功的逻辑部分, ...
一周排行
  • /* Stern-Brocot代数系统 Stern-Brocot树是一种生成所有非负的最简分数m/n的美妙方式. 其基本方式是从(0/1, 1/0)这两个分数开始, 根据需要反复执行如下操作: 在相邻的分数 m/n ...
  • 因为在网上看了一下破解access密码的几个vb函数,就拿出来和大家一起分享一下,教大家用vb来编写一个简单的工具吧. 打开vb,新建一个标准EXE工程,添加3个label控件,3个text控件,2个command控 ...
  • 7月29日消息,据国外媒体报道,针对雅虎和微软即将达成的搜索合作协议,有分析师认为,把搜索业务转让给微软,雅虎将失去核心竞争力. 周一有消息称,微软和雅虎最早将于本周宣布搜索合作协议.最新消息显示,双方的交易将采用营 ...
  • 今天编写Android程序,遇到一个问题: fragment是activity的一部分,具有高度的自由性.我编写了一个Fragment程序,在其中添加了Spinner控件(就是普通的添加方式),但是就是运用Array ...
  • redis-search4j是一款基于redis的搜索组件. 特点 1.基于redis,性能高效 2.实时更新索引 3.支持Suggest前缀.拼音查找(AutoComplete功能) 4.支持单个或多个分词搜索 5 ...
  • 1. 读写文件的步骤:      创建一个文件流 -- 创建相应的读写器 -- 执行读写操作 -- 关闭读写器 -- 关闭文件流      创建一个文件流:   FileStream objfs = new File ...
  • 经过了一个多月的时间,今天终于可以回到正轨了,继续开始刷CF. 题目大意: 给出一个只有括号的字符串,求最长"匹配"子串的长度和数量. 解题思路: 设置数组记录匹配括号段的开头. 下面是代码: # ...
  • 我使用的是163的邮箱.由于没有开通pop/stmp协议导致出现这个异常. 邮箱设置里开通这两个协议即可.
  • 背景: 大学期间学习过一段时间的JavaEE,不算非常熟悉.后来学习并在工作中更多是iOS开发,iOS的水平属于中上.对技术已经有一定熟知程度.最近为了写一些东西,需要用到Java写后台. 流程: 1.下载JDK 和 ...
  • 嵌入式Linux之我行,主要讲述和总结了本人在学习嵌入式linux中的每个步骤.一为总结经验,二希望能 给想入门嵌入式Linux的朋友提供方便.如有错误之处,谢请指正. 一.开发环境 Fedora 9 开发板:Min ...