Java 冒泡排序、快速排序?qū)嵗a
冒泡排序
冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪(fǎng)過(guò)要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪(fǎng)數(shù)列的工作是重復(fù)地 進(jìn)行直到?jīng)]有再需要交換,也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序的算法實(shí)現(xiàn)如下:【排序后,數(shù)組從小到大排列】
/** * 冒泡排序 * 比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。 * 對(duì)每一對(duì)相鄰元素作同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn),最后的元素應(yīng)該會(huì)是最大的數(shù)。 * 針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。 * 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。 * @param numbers 需要排序的整型數(shù)組 */ public static void bubbleSort(int[] numbers) { int temp = 0; int size = numbers.length; for(int i = 0 ; i < size-1; i ++) { for(int j = 0 ;j < size-1-i ; j++) { if(numbers[j] > numbers[j+1]) //交換兩數(shù)位置 { temp = numbers[j]; numbers[j] = numbers[j+1]; numbers[j+1] = temp; } } } }
快速排序
快速排序的基本思想:
通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分,其中一部分記錄的關(guān)鍵字均比另一部分關(guān)鍵字小,則分別對(duì)這兩部分繼續(xù)進(jìn)行排序,直到整個(gè)序列有序。
把整個(gè)序列看做一個(gè)數(shù)組,把第零個(gè)位置看做中軸,和最后一個(gè)比,如果比它小交換,比它大不做任何處理;交換了以后再和小的那端比,比它小不交換,比他大交換。這樣循環(huán)往復(fù),一趟排序完成,左邊就是比中軸小的,右邊就是比中軸大的,然后再用分治法,分別對(duì)這兩個(gè)獨(dú)立的數(shù)組進(jìn)行排序。
代碼實(shí)現(xiàn)如下:
1.查找中軸(最低位作為中軸)所在位置
/** * 查找出中軸(默認(rèn)是最低位low)的在numbers數(shù)組排序后所在位置 * * @param numbers 帶查找數(shù)組 * @param low 開(kāi)始位置 * @param high 結(jié)束位置 * @return 中軸所在位置 */ public static int getMiddle(int[] numbers, int low,int high) { int temp = numbers[low]; //數(shù)組的第一個(gè)作為中軸 while(low < high) { while(low < high && numbers[high] > temp) { high--; } numbers[low] = numbers[high];//比中軸小的記錄移到低端 while(low < high && numbers[low] < temp) { low++; } numbers[high] = numbers[low] ; //比中軸大的記錄移到高端 } numbers[low] = temp ; //中軸記錄到尾 return low ; // 返回中軸的位置 }
2、 遞歸形式的分治排序算法:
/** * * @param numbers 帶排序數(shù)組 * @param low 開(kāi)始位置 * @param high 結(jié)束位置 */ public static void quickSort(int[] numbers,int low,int high) { if(low < high) { int middle = getMiddle(numbers,low,high); //將numbers數(shù)組進(jìn)行一分為二 quickSort(numbers, low, middle-1); //對(duì)低字段表進(jìn)行遞歸排序 quickSort(numbers, middle+1, high); //對(duì)高字段表進(jìn)行遞歸排序 } }
3、快速排序提供方法調(diào)用
/** * 快速排序 * @param numbers 帶排序數(shù)組 */ public static void quick(int[] numbers) { if(numbers.length > 0) //查看數(shù)組是否為空 { quickSort(numbers, 0, numbers.length-1); } }
分析:
快速排序是通常被認(rèn)為在同數(shù)量級(jí)(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時(shí),快排序反而蛻化為冒泡排序。為改進(jìn)之,通常以“三者取中法”來(lái)選取基準(zhǔn)記錄,即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄??焖倥判蚴且粋€(gè)不穩(wěn)定的排序方法。
方法測(cè)試
打印函數(shù):
public static void printArr(int[] numbers) { for(int i = 0 ; i < numbers.length ; i ++ ) { System.out.print(numbers[i] + ","); } System.out.println(""); }
測(cè)試:
public static void main(String[] args) { int[] numbers = {10,20,15,0,6,7,2,1,-5,55}; System.out.print("排序前:"); printArr(numbers); bubbleSort(numbers); System.out.print("冒泡排序后:"); printArr(numbers); quick(numbers); System.out.print("快速排序后:"); printArr(numbers); }
結(jié)果:
排序前:10,20,15,0,6,7,2,1,-5,55,
冒泡排序后:-5,0,1,2,6,7,10,15,20,55,
快速排序后:-5,0,1,2,6,7,10,15,20,55,
以上所述是小編給大家介紹的Java 冒泡排序、快速排序?qū)嵗a,希望對(duì)大家有所幫助,如果大家有任何疑問(wèn)請(qǐng)給我留言,小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持!
- Java編程基于快速排序的三個(gè)算法題實(shí)例代碼
- Java基于分治法實(shí)現(xiàn)的快速排序算法示例
- Java編程實(shí)現(xiàn)快速排序及優(yōu)化代碼詳解
- java簡(jiǎn)單快速排序?qū)嵗馕?/a>
- java 算法之快速排序?qū)崿F(xiàn)代碼
- JAVA一個(gè)快速排序?qū)崿F(xiàn)代碼
- 圖文講解Java中實(shí)現(xiàn)quickSort快速排序算法的方法
- Java編程中快速排序算法的實(shí)現(xiàn)及相關(guān)算法優(yōu)化
- 詳解Java中使用泛型實(shí)現(xiàn)快速排序算法的方法
- 詳解Java雙軸快速排序算法
相關(guān)文章
springboot項(xiàng)目中全局設(shè)置用UTC+8
本文主要介紹了springboot項(xiàng)目中全局設(shè)置用UTC+8,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04spring-data-jpa中findOne與getOne的區(qū)別說(shuō)明
這篇文章主要介紹了spring-data-jpa中findOne與getOne的區(qū)別說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-11-11SpringBoot生成PDF的五種實(shí)現(xiàn)方法總結(jié)
這篇文章主要介紹了SpringBoot生成PDF的五種實(shí)現(xiàn)方法,在開(kāi)發(fā)中經(jīng)常會(huì)遇到需要進(jìn)行對(duì)一些數(shù)據(jù)進(jìn)行動(dòng)態(tài)導(dǎo)出PDF文件,然后讓用戶(hù)自己選擇是否需要打印出來(lái),這篇文章我們來(lái)介紹五種實(shí)現(xiàn)方法,需要的朋友可以參考下2024-10-10Java中的線(xiàn)程中斷機(jī)制和LockSupport詳解
這篇文章主要介紹了Java中的線(xiàn)程中斷機(jī)制和LockSupport詳解,在Java中沒(méi)有辦法立即停止一條線(xiàn)程,然而停止線(xiàn)程卻顯得尤為重要,如取消一個(gè)耗時(shí)操作,因此,Java提供了一種用于停止線(xiàn)程的協(xié)商機(jī)制中斷,也即中斷標(biāo)識(shí)協(xié)商機(jī)制,需要的朋友可以參考下2023-09-09利用ScriptEngineManager實(shí)現(xiàn)字符串公式靈活計(jì)算的方法
今天小編就為大家分享一篇利用ScriptEngineManager實(shí)現(xiàn)字符串公式靈活計(jì)算的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-07-07從Myeclipse 導(dǎo)入到eclipse中無(wú)法識(shí)別為 web項(xiàng)目 問(wèn)題的解決步驟
這篇文章主要介紹了從Myeclipse 導(dǎo)入到eclipse中無(wú)法識(shí)別為 web項(xiàng)目 問(wèn)題的解決步驟,需要的朋友可以參考下2018-05-05