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表单登陆,并且可以处理是否登陆成功的逻辑部分, ...
一周排行
  • 给出一棵树,判断 以 某个 节点 为 根 的子树 有多少个节点有苹果.. 知道要用树状数组求和,但是 每个子树节点编号不连续,头疼,后来看了一些大神的报告才 恍然大悟. 可以先进行一次 dfs 后序遍历,对 每个节点 ...
  • 方式1:使用sinaapp提供的接口生成,HTML代码如下: <html> <body> <h3>qrcode based on sinaapp:</h3> <i ...
  • 这里将介绍使用tolua++将自定义的C++类嵌入,让lua脚本使用 一般过程: 自定义类 -> 使用tolua++工具编译到LuaCoco2d.cpp中 -> lua调用 步骤一:自定义一个C++类,我 ...
  •  今天终于开博开始记录在IT界成长的经历,上了CSDN这么久,这还是第一次写博客,希望以后会越来越好!
  • 这个时候是该好好地反省一下自己了!以前的时候为了队伍能打出更多的题,我硬是看了ACM的很多模块!也会了很多的模板!但是现在我痛苦地发现比赛还是我一人单挑的局面!现在我也遇见了一个瓶颈了,那就是算法题会思路或者是赛后才 ...
  • ipa本身是一个zip文件改后缀后解压缩就能看到应用内使用的资源文件 其中png图片资源xcode打包的时候做了些手脚 具体怎么处理的这里不做解释 下边提供一个python脚本 from struct import ...
  • 200
    #include<stdio.h> int main(void) {          int i,n;          double product;            printf(" ...
  • 题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2561 题意:给定一个边带正权的连通无向图G= (V,E),其中N=V,M=E,N个点从1到N依次编号,给 ...
  • 注意:原文转自:http://www.cnblogs.com/JackOne/archive/2013/02/19/DeepLearning-FirstBoold.html由于文章写得很好,所以转载到此.     D ...