排序高级之交换排序_奇偶排序

简介:

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

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

处理器数组的排序

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

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

Batcher奇偶归并排序

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

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


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

奇偶排序动态图:



代码实现:

[html]  view plain  copy
 print ? 在CODE上查看代码片 派生到我的代码片
  1. package com.baobaotao.test;  
  2. /**  
  3.  * 排序研究  
  4.  * @author benjamin(吴海旭)  
  5.  * @email benjaminwhx@sina.com / 449261417@qq.com  
  6.  *  
  7.  */  
  8. public class Sort {  
  9.     /**  
  10. <span style="white-space:pre">    </span> * 奇偶排序  
  11. <span style="white-space:pre">    </span> * @param array  
  12. <span style="white-space:pre">    </span> */  
  13.     public static void batcherSort(int[] array) {  
  14.         int length = array.length ;  
  15.         boolean flag = true ;  
  16.         while(true) {  
  17.             flag = true ;  
  18.             for(int i=1;i<length-1;i+=2) {  
  19.                 if(array[i] > array[i+1]) {  
  20.                     swap(array, i, i+1) ;  
  21.                     flag = false ;  
  22.                 }  
  23.             }  
  24.             for(int i=0;i<length-1;i+=2) {  
  25.                 if(array[i] > array[i+1]) {  
  26.                     swap(array, i, i+1) ;  
  27.                     flag = false ;  
  28.                 }  
  29.             }  
  30.             if(flag) break ;  
  31.             printArr(array) ;  
  32.         }  
  33.     }  
  34.     /**  
  35.      * 按从小到大的顺序交换数组  
  36.      * @param a 传入的数组  
  37.      * @param b 传入的要交换的数b  
  38.      * @param c 传入的要交换的数c  
  39.      */  
  40.     public static void swap(int[] a, int b, int c) {  
  41.         int temp = 0 ;  
  42.         if(b < c) {  
  43.             if(a[b] > a[c]) {  
  44.                 temp = a[b] ;  
  45.                 a[b] = a[c] ;  
  46.                 a[c] = temp ;   
  47.             }  
  48.         }  
  49.     }  
  50.       
  51.     /**  
  52.      * 打印数组  
  53.      * @param array  
  54.      */  
  55.     public static void printArr(int[] array) {  
  56.         for(int c : array) {  
  57.             System.out.print(c + " ");  
  58.         }  
  59.         System.out.println();  
  60.     }  
  61.       
  62.     public static void main(String[] args) {  
  63.         int[] number={11,95,45,15,78,84,51,24,12} ;  
  64.         batcherSort(number) ;  
  65.     }  
  66. }  

输出分析:

[html]  view plain  copy
 print ? 在CODE上查看代码片 派生到我的代码片
  1. 11 45 15 95 51 78 12 84 24   
  2. 11 15 45 51 12 95 24 78 84   
  3. 11 15 12 45 24 51 78 95 84   
  4. 11 12 15 24 45 51 78 84 95   

转载请注明:http://blog.csdn.net/benjamin_whx/article/details/42456755
目录
相关文章
|
1月前
|
存储 搜索推荐 算法
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
24 1
|
6月前
|
搜索推荐
排序——交换排序
排序——交换排序
49 0
|
6月前
|
机器学习/深度学习
数据结构实验之排序二:交换排序
数据结构实验之排序二:交换排序
|
算法 搜索推荐 Shell
Shell编程之数组排序算法(冒泡排序、直接选择排序、反转排序)
1、数组排序(使用tr、sort、for) 操作步骤; 使用tr命令将数组内每个元素之间的空格替换为换行符; 之后使用sort命令按从小到大重新排序; 最后使用for循环遍历排序后的元素值。
480 0
|
机器学习/深度学习 搜索推荐
八大排序(三)--------简单选择排序
八大排序(三)--------简单选择排序
47 0
|
机器学习/深度学习 搜索推荐 算法
八大排序(四)--------直接插入排序
八大排序(四)--------直接插入排序
48 0
|
算法
排序篇(三)----交换排序
排序篇(三)----交换排序
42 0
【八大排序(九)】计数排序-非比较排序法
【八大排序(九)】计数排序-非比较排序法
|
算法
排序(3)之交换排序
今天小编给大家带来交换排序的内容,对于交换排序中的快速排序在理解上会相对困难一点,小编这里会配合图片给大家细细讲解。那么现在就开始我们今天的主题。
80 0
|
算法 搜索推荐