利用Java如何实现一个二分插入排序

这篇文章给大家介绍利用Java如何实现一个二分插入排序,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

为都昌等地区用户提供了全套网页设计制作服务,及都昌网站建设行业解决方案。主营业务为成都网站建设、网站设计、都昌网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!

一、折半插入排序(二分插入排序)

将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法。在处理A[i]时,A[0]……A[i-1]已经按关键码值排好序。所谓折半比较,就是在插入A[i]时,取A[i-1/2]的关键码值与A[i]的关键码值进行比较,如果A[i]的关键码值小于A[i-1/2]的关键码值,则说明A[i]只能插入A[0]到A[i-1/2]之间,故可以在A[0]到A[i-1/2-1]之间继续使用折半比较;否则只能插入A[i-1/2]到A[i-1]之间,故可以在A[i-1/2+1]到A[i-1]之间继续使用折半比较。如此担负,直到最后能够确定插入的位置为止。一般在A[k]和A[r]之间采用折半,其中间结点为A[k+r/2],经过一次比较即可排除一半纪录,把可能插入的区间减小了一半,故称为折半。执行折半插入排序的前提是文件纪录必须按顺序存储。

二、算法原理

折半插入排序的算法思想:

算法的基本过程:
(1)计算 0 ~ i-1 的中间点,用 i 索引处的元素与中间值进行比较,如果 i 索引处的元素大,说明要插入的这个元素应该在中间值和刚加入i索引之间,反之,就是在刚开始的位置 到中间值的位置,这样很简单的完成了折半;
(2)在相应的半个范围里面找插入的位置时,不断的用(1)步骤缩小范围,不停的折半,范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方;
(3)确定位置之后,将整个序列后移,并将元素插入到相应位置。

利用Java如何实现一个二分插入排序

三、代码实现

public class BinarySort { 
  public static void binarySort(int[] source) { 
    int i, j; 
    int high, low, mid; 
    int temp; 
    for (i = 1; i < source.length; i++) { 
      // 查找区上界 
      low = 0; 
      // 查找区下界 
      high = i - 1; 
      //将当前待插入记录保存在临时变量中 
      temp = source[i]; 
      while (low <= high) { 
        // 找出中间值 
        // mid = (low + high) / 2; 
        mid = (low + high) >> 1; 
        //如果待插入记录比中间记录小 
        if (temp=low; j--) { 
        source[j + 1] = source[j]; 
      } 
      //将待插入记录回填到正确位置.  
      source[low] = temp; 
      System.out.print("第" + i + "趟排序:"); 
      printArray(source); 
    } 
  } 
 
  private static void printArray(int[] source) { 
    for (int i = 0; i < source.length; i++) { 
      System.out.print("\t" + source[i]); 
    } 
    System.out.println(); 
  } 
 
  public static void main(String[] args) { 
    int source[] = new int[] { 12, 15, 9, 14, 4, 18, 23, 6 }; 
    System.out.print("初始关键字:"); 
    printArray(source); 
    System.out.println(""); 
 
    binarySort(source); 
 
    System.out.print("\n\n排序后结果:"); 
    printArray(source); 
  } 
} 

四、运行结果

初始关键字: 12 15 9  14 4  18 23 6 
 
第1趟排序: 12 15 9  14 4  18 23 6 
第2趟排序: 9  12 15 14 4  18 23 6 
第3趟排序: 9  12 14 15 4  18 23 6 
第4趟排序: 4  9  12 14 15 18 23 6 
第5趟排序: 4  9  12 14 15 18 23 6 
第6趟排序: 4  9  12 14 15 18 23 6 
第7趟排序: 4  6  9  12 14 15 18 23 
 
 
排序后结果: 4  6  9  12 14 15 18 23 

关于利用Java如何实现一个二分插入排序就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。


分享题目:利用Java如何实现一个二分插入排序
本文URL:http://scyanting.com/article/pdopoh.html