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

2024-08-22 23:32
文章标签 排序 交换 高级 奇偶

本文主要是介绍排序高级之交换排序_奇偶排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

处理器数组的排序

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

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

Batcher奇偶归并排序

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

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


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

奇偶排序动态图:



代码实现:

package com.baobaotao.test;
/*** 排序研究* @author benjamin(吴海旭)* @email benjaminwhx@sina.com / 449261417@qq.com**/
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 

转载请注明:http://blog.csdn.net/benjamin_whx/article/details/42456755

这篇关于排序高级之交换排序_奇偶排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1097712

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

hdu1010 奇偶剪枝

恰好t时间到达 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.Arrays;import

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

Java基础回顾系列-第七天-高级编程之IO

Java基础回顾系列-第七天-高级编程之IO 文件操作字节流与字符流OutputStream字节输出流FileOutputStream InputStream字节输入流FileInputStream Writer字符输出流FileWriter Reader字符输入流字节流与字符流的区别转换流InputStreamReaderOutputStreamWriter 文件复制 字符编码内存操作流(

Java基础回顾系列-第五天-高级编程之API类库

Java基础回顾系列-第五天-高级编程之API类库 Java基础类库StringBufferStringBuilderStringCharSequence接口AutoCloseable接口RuntimeSystemCleaner对象克隆 数字操作类Math数学计算类Random随机数生成类BigInteger/BigDecimal大数字操作类 日期操作类DateSimpleDateForma