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

简介:

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

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

处理器数组的排序

在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连。所有处理器可同时与邻居进行比较、交换操作,交替以奇-偶、偶-奇的顺序。该算法由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
目录
相关文章
|
12月前
快排&超详细,Leetcode排序数组题目带你升华掌握(上)
快排&超详细,Leetcode排序数组题目带你升华掌握
55 0
|
算法 搜索推荐 Shell
Shell编程之数组排序算法(冒泡排序、直接选择排序、反转排序)
1、数组排序(使用tr、sort、for) 操作步骤; 使用tr命令将数组内每个元素之间的空格替换为换行符; 之后使用sort命令按从小到大重新排序; 最后使用for循环遍历排序后的元素值。
471 0
|
12月前
|
测试技术 编译器 Shell
快排&超详细,Leetcode排序数组题目带你升华掌握(下)
快排&超详细,Leetcode排序数组题目带你升华掌握(上)
132 0
|
12月前
|
机器学习/深度学习 搜索推荐
八大排序(三)--------简单选择排序
八大排序(三)--------简单选择排序
44 0
|
12月前
|
机器学习/深度学习 搜索推荐 算法
八大排序(四)--------直接插入排序
八大排序(四)--------直接插入排序
43 0
|
机器学习/深度学习 算法 搜索推荐
【八大排序之插入和选择排序】
【八大排序之插入和选择排序】
90 0
【八大排序之交换与归并排序】(一)
【八大排序之交换与归并排序】(一)
47 0
|
搜索推荐 算法
【八大排序之交换与归并排序】(二)
【八大排序之交换与归并排序】(二)
48 0
|
算法 搜索推荐 C语言
【排序】排序这样写才对Ⅱ -冒泡排序与快速排序Ⅰ
常见的排序算法有这些.将会分成几个章节讲完,感兴趣的uu们可以关注下我的排序专栏,方便和后期观看.
81 0
leetcode905–按奇偶排序数组(经典/原地排序)
leetcode905–按奇偶排序数组(经典/原地排序)