java交换排序之奇偶排序实现方法

首页 > 软件编程 > java 更新日期: 2016-01-17
这篇文章主要介绍了java交换排序之奇偶排序实现方法,实例分析了奇偶排序的原理与具体实现技巧,非常具有实用价值,需要的朋友可以参考下

本文实例讲述了java交换排序之奇偶排序实现方法。分享给大家供大家参考。具体如下:

奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序。

该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换。下一步重复该操作,但针对所有的(偶-奇)位置数字对。如此交替进行下去。

处理器数组的排序

在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连。所有处理器可同时与邻居进行比较、交换操作,交替以奇-偶、偶-奇的顺序。该算法由Habermann在1972年最初发表并展现了在并行处理上的效率。

该算法可以有效地延伸到每个处理器拥有多个值的情况。在Baudet–Stevenson奇偶合并分区算法中,每个处理器在每一步对自己所拥有的子数组进行排序,然后与邻居执行合并分区或换位合并。

Batcher奇偶归并排序

Batcher奇偶归并排序是一种相关但更有效率的排序算法,采用比较-交换和完美-洗牌操作。

Batcher的方法在拥有广泛互连的并行计算处理器上效率不错。


最差时间复杂度 \Theta(n^2)

奇偶排序动态图如下所示:

java交换排序之奇偶排序实现方法

代码实现:

package com.baobaotao.test; 
/** 
 * 排序研究 
 * 
 */ 
public class Sort { 
  /** 
<span style="white-space:pre">  </span> * 奇偶排序 
<span style="white-space:pre">  </span> * @param array 
<span style="white-space:pre">  </span> */ 
  public static void batcherSort(int[] array) { 
    int length = array.length ; 
    boolean flag = true ; 
    while(true) { 
      flag = true ; 
      for(int i=1;i<length-1;i+=2) { 
        if(array[i] > array[i+1]) { 
          swap(array, i, i+1) ; 
          flag = false ; 
        } 
      } 
      for(int i=0;i<length-1;i+=2) { 
        if(array[i] > array[i+1]) { 
          swap(array, i, i+1) ; 
          flag = false ; 
        } 
      } 
      if(flag) break ; 
      printArr(array) ; 
    } 
  } 
  /** 
   * 按从小到大的顺序交换数组 
   * @param a 传入的数组 
   * @param b 传入的要交换的数b 
   * @param c 传入的要交换的数c 
   */ 
  public static void swap(int[] a, int b, int c) { 
    int temp = 0 ; 
    if(b < c) { 
      if(a[b] > a[c]) { 
        temp = a[b] ; 
        a[b] = a[c] ; 
        a[c] = temp ;  
      } 
    } 
  } 
   
  /** 
   * 打印数组 
   * @param array 
   */ 
  public static void printArr(int[] array) { 
    for(int c : array) { 
      System.out.print(c + " "); 
    } 
    System.out.println(); 
  } 
   
  public static void main(String[] args) { 
    int[] number={11,95,45,15,78,84,51,24,12} ; 
    batcherSort(number) ; 
  } 
}

输出分析:

11 45 15 95 51 78 12 84 24
11 15 45 51 12 95 24 78 84
11 15 12 45 24 51 78 95 84
11 12 15 24 45 51 78 84 95

希望本文所述对大家的java程序设计有所帮助。


> 本站内容系网友提交或本网编辑转载,其目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题,请及时与本网联系,我们将在第一时间删除内容!

相关文章
  • Java编程实现中英混合字符串数组按首字母排序的方法
    这篇文章主要介绍了Java编程实现中英混合字符串数组按首字母排序的方法,涉及Java字符串操作及拼音转换的相关使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下本文实例讲述了Java编程实现中英混合字符串数组按首字母排序的方法.分享给大家供大家参考,具体如下: 在Java中对于字符串数组的排序,我们可以使用Arrays.sort(String[])方法很便 ...
  • 用Java集合中的Collections.sort方法如何对list排序(两种方法)
    本文通过两种方法给大家介绍java集合中的Collections.sort方法对list排序,第一种方式是list中的对象实现Comparable接口,第二种方法是根据Collections.sort重载方法实现,对collections.sort方法感兴趣的朋友一起学习吧第一种是list中的对象实现Comparable接口,如下: /** * 根据orde ...
  • java冒泡排序和选择排序示例
    java冒泡排序和选择排序示例
    这篇文章主要介绍了java冒泡排序和选择排序示例,需要的朋友可以参考下冒泡排序(BubbleSort)的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面.即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后.然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后.至此第一趟结束,将最大的数放到 ...
  • PHP按指定键值对二维数组进行排序的方法
    这篇文章主要介绍了PHP按指定键值对二维数组进行排序的方法,涉及PHP二维数组的遍历及array_multisort函数的使用技巧,需要的朋友可以参考下本文实例讲述了PHP按指定键值对二维数组进行排序的方法.分享给大家供大家参考,具体如下: 问题: 有数组: 代码如下:array(0=>array('id'=>1,'price'=>50), ...
  • Django中对数据查询结果进行排序的方法
    这篇文章主要介绍了Django中对数据查询结果进行排序的方法,利用Python代码代替SQL进行一些简单的操作,需要的朋友可以参考下在你的 Django 应用中,你或许希望根据某字段的值对检索结果排序,比如说,按字母顺序. 那么,使用 order_by() 这个方法就可以搞定了. >>> Publisher.objects.order_by ...
  • zencart新进商品的随机排序修改方法
    由于新进商品的数量可能比页面上能显示的数量多,所以采用的是随机显示的方式.如果想改为按时间顺序显示,可以按照radnows提供的 方法修改.记住使用文件替代zencart新进商品的随机排序修改方法第一步:首先,新进商品可以自己定义时间段:商店设置-最大值-新进商品的定义 zencart新进商品的随机排序修改方法第二步: 修改首页上新进商品: /include ...
猜你喜欢