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

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

基本思想：

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

C++实例：

#include<iostream>

using namespace std;

void HalfSort(int *array,int Length)
{//定义最低，最高，中间值，待插入数据，插入位置
	int low,high,middle,temp,index,i,j;
	for(i=1;i<Length;i++)  //控制插入的元素，第一次从下标为1的元素开始
	{                     //，将前面array[0]的当成已经排好序的数列,然后逐个插入
	  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
		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<Length;i++)
	{
	  cout<<array[i]
	      <<"  "; 
	}
	cout<<endl;
}
void main()
{
	int array[]={63,4,24,1,3,15};
	int Length=sizeof(array)/sizeof(array[0]);//计算长度
	HalfSort(array,Length);

}

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);
        }
    }
}

以上结果为：

java实例：

package Sort;

public 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;
	}
	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);
		
	}

}

结果：

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

            以上代码中有什么需要改进的欢迎留言^_^

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

原文：http://blog.csdn.net/hc666/article/details/49514385