java交換排序之奇偶排序?qū)崿F(xiàn)方法
本文實(shí)例講述了java交換排序之奇偶排序?qū)崿F(xiàn)方法。分享給大家供大家參考。具體如下:
奇偶排序,或奇偶換位排序,或磚排序,是一種相對(duì)簡(jiǎn)單的排序算法,最初發(fā)明用于有本地互連的并行計(jì)算。這是與冒泡排序特點(diǎn)類似的一種比較排序。
該算法中,通過比較數(shù)組中相鄰的(奇-偶)位置數(shù)字對(duì),如果該奇偶對(duì)是錯(cuò)誤的順序(第一個(gè)大于第二個(gè)),則交換。下一步重復(fù)該操作,但針對(duì)所有的(偶-奇)位置數(shù)字對(duì)。如此交替進(jìn)行下去。
處理器數(shù)組的排序
在并行計(jì)算排序中,每個(gè)處理器對(duì)應(yīng)處理一個(gè)值,并僅有與左右鄰居的本地互連。所有處理器可同時(shí)與鄰居進(jìn)行比較、交換操作,交替以奇-偶、偶-奇的順序。該算法由Habermann在1972年最初發(fā)表并展現(xiàn)了在并行處理上的效率。
該算法可以有效地延伸到每個(gè)處理器擁有多個(gè)值的情況。在Baudet–Stevenson奇偶合并分區(qū)算法中,每個(gè)處理器在每一步對(duì)自己所擁有的子數(shù)組進(jìn)行排序,然后與鄰居執(zhí)行合并分區(qū)或換位合并。
Batcher奇偶?xì)w并排序
Batcher奇偶?xì)w并排序是一種相關(guān)但更有效率的排序算法,采用比較-交換和完美-洗牌操作。
Batcher的方法在擁有廣泛互連的并行計(jì)算處理器上效率不錯(cuò)。
最差時(shí)間復(fù)雜度 \Theta(n^2)
奇偶排序動(dòng)態(tài)圖如下所示:
代碼實(shí)現(xiàn):
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) ; } } /** * 按從小到大的順序交換數(shù)組 * @param a 傳入的數(shù)組 * @param b 傳入的要交換的數(shù)b * @param c 傳入的要交換的數(shù)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 ; } } } /** * 打印數(shù)組 * @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
希望本文所述對(duì)大家的java程序設(shè)計(jì)有所幫助。
- java數(shù)據(jù)結(jié)構(gòu)與算法之奇偶排序算法完整示例
- 簡(jiǎn)單講解奇偶排序算法及在Java數(shù)組中的實(shí)現(xiàn)
- c語言實(shí)現(xiàn)奇偶排序算法
- C語言對(duì)棧的實(shí)現(xiàn)基本操作
- 利用C語言實(shí)現(xiàn)2048小游戲的方法
- C語言 數(shù)據(jù)結(jié)構(gòu)之鏈表實(shí)現(xiàn)代碼
- 詳解C語言gets()函數(shù)與它的替代者fgets()函數(shù)
- C語言 動(dòng)態(tài)內(nèi)存分配的詳解及實(shí)例
- 常用Hash算法(C語言的簡(jiǎn)單實(shí)現(xiàn))
- C語言 奇偶排序算法詳解及實(shí)例代碼
相關(guān)文章
Spring?Security認(rèn)證器實(shí)現(xiàn)過程詳解
一些權(quán)限框架一般都包含認(rèn)證器和決策器,前者處理登陸驗(yàn)證,后者處理訪問資源的控制,這篇文章主要介紹了Spring?Security認(rèn)證器實(shí)現(xiàn)過程,需要的朋友可以參考下2022-06-06java將XML文檔轉(zhuǎn)換成json格式數(shù)據(jù)的示例
本篇文章主要介紹了java將XML文檔轉(zhuǎn)換成json格式數(shù)據(jù)的示例,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-12-12Java+OpenCV調(diào)用攝像頭實(shí)現(xiàn)拍照功能
隨著我們對(duì)環(huán)境、Mat基本使用越來越熟練、Java Swing也逐步熟悉了起來。本文將通過OpenCV驅(qū)動(dòng)攝像頭實(shí)現(xiàn)識(shí)臉和拍照功能,需要的可以參考一下2022-03-03JavaWeb項(xiàng)目web.xml中出現(xiàn)Element xxx is not al
這篇文章主要介紹了JavaWeb項(xiàng)目web.xml中出現(xiàn)Element xxx is not allowed here問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11實(shí)現(xiàn)quartz定時(shí)器及quartz定時(shí)器原理介紹
Quartz是一個(gè)大名鼎鼎的Java版開源定時(shí)調(diào)度器,功能強(qiáng)悍,使用方便,下面我們看看如何使用它2013-12-12SpringBoot整合Mybatis-plus實(shí)現(xiàn)多級(jí)評(píng)論功能
本文介紹了如何使用SpringBoot整合Mybatis-plus實(shí)現(xiàn)多級(jí)評(píng)論功能,同時(shí)提供了數(shù)據(jù)庫的設(shè)計(jì)和詳細(xì)的后端代碼,前端界面使用的Vue2,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2023-05-05