java應用冒泡排序對數組停止排序。本站提示廣大學習愛好者:(java應用冒泡排序對數組停止排序)文章只能為提供參考,不一定能成為您想要的結果。以下是java應用冒泡排序對數組停止排序正文
本文實例講述了java應用冒泡排序對數組停止排序的辦法。分享給年夜家供年夜家參考。詳細以下:
1、冒泡排序:
應用冒泡排序對數組停止排序
2、根本概念:
順次比擬相鄰的兩個數,將小數放在後面,年夜數放在前面。即在第一趟:起首比擬第1個和第2個數,將小數放前,年夜數放後。然後比擬第2個數和第3個數,將小數放前,年夜數放後,如斯持續,直至比擬最初兩個數,將小數放前,年夜數放後。至此第一趟停止,將最年夜的數放到了最初。在第二趟:仍從第一對數開端比擬(由於能夠因為第2個數和第3個數的交流,使得第1個數不再小於第2個數),將小數放前,年夜數放後,一向比擬到倒數第二個數(倒數第一的地位上曾經是最年夜的),第二趟停止,在倒數第二的地位上獲得一個新的最年夜數(其其實全部數列中是第二年夜的數)。如斯下去,反復以上進程,直至終究完成排序。
3、完成思緒:
用二重輪回完成,外輪回變量設為i,內輪回變量設為j。假設有n個數須要停止排序,則外輪回反復n-1次,內輪回順次反復n-1,n-2,...,1次。每次停止比擬的兩個元素都是與內輪回j有關的,它們可以分離用a[j]和a[j+1]標識,i的值順次為1,2,...,n-1,關於每個i,j的值順次為0,1,2,...n-i 。
設數組長度為N:
1.比擬相鄰的前後二個數據,假如後面數據年夜於前面的數據,就將二個數據交流。
2.如許對數組的第0個數據到N-1個數據停止一次遍歷後,最年夜的一個數據就“沉”到數組第N-1個地位。
3.N=N-1,假如N不為0就反復後面二步,不然排序完成。
4、java代碼完成:
package ArrayDemo; /** * @author pplsunny * @category .21 */ public class ArrayDemo { /** * 用加強for輪回輸入排序成果 */ public static void main(String[] args) { int[] a = { 2, 4, 76, 12, 34, 23, 86 }; ArrayDemo.bubbleSort(a); for (int b : a) { System.out.print(b + " "); } } /* * 冒泡排序函數,界說為靜態的便利應用, * 也是開辟中界說對象類的一個辦法 */ public static void bubbleSort(int a[]) { for (int i = 1; i < a.length; i++) { //這是掌握趟數 for (int j = 0; j < a.length - i; j++) { //j < a.length - i,比擬元素的個數 if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } } }
5、機能剖析:
若記載序列的初始狀況為"正序",則冒泡排序進程只需停止一趟排序,在排序進程中只需停止n-1次比擬,且不挪動記載;反之,若記載序列的初始狀況為"逆序",則需停止n(n-1)/2次比擬和記載挪動。是以冒泡排序總的時光龐雜度為O(n*n)。
6、算法優化:
冒泡排序法存在的缺乏及改良辦法:
第一,在排序進程中,履行完最初的排序後,固然數據已全體排序完整,但法式沒法斷定能否完成排序,為懂得決這一缺乏,可設置一個標記位flag,將其初始值設置為非0,表現被排序的表是一個無序的表,每次排序開端前設置flag值為0,在停止數據交流時,修正flag為非0。在新一輪排序開端時,檢討此標記,若此標記為0,表現上一次沒有做過交流數據,則停止排序;不然停止排序;
/* * 冒泡排序函數改良版 */ public static void BubbleSort(int[] a) { boolean flag = true; while (flag) { flag = false; for (int i = 0; i < a.length - 1; i++) { for (int j = 0; j < a.length - i ; j++) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; flag = true; } } if (!flag) break; // 假如沒有產生交流,則加入輪回 } } }
第2、在冒泡排序中,一趟掃描有能夠有數據交流,也有能夠有一次或屢次數據交流,在傳統的冒泡排序算法及最近幾年來的一些改良的算法中,只記載一趟掃描有沒有數據交流的信息,對數據交流產生的地位信息則不予處置。為了充足應用這一信息,可以在一趟全局掃描中,對每反序數據對停止部分冒泡排序處置,稱之為部分冒泡排序。部分冒泡排序與冒泡排序算法具有雷同的時光龐雜度,而且在正序和逆序的情形下,所需的症結字的比擬次數和挪動次數完整雷同。因為部分冒泡排序和冒泡排序的數據挪動次數老是雷同的,而部分冒泡排序所需症結字的比擬次數常少於冒泡排序,這意味著部分冒泡排序極可能在均勻比擬次數上對冒泡排序有所改良,當比擬次數較少的長處缺乏以抵消其法式龐雜度所帶來的額定開支,而當數據量較年夜時,部分冒泡排序的時光機能則顯著優於冒泡排序。關於N個無序數據,我們在停止一趟冒泡排序時,假如第k個數據和第k+1個數據逆序,那末對第k+1個數據停止一趟向前的冒泡排序,使其挪動到適合的地位,也就是說讓後面k+1個數據調理為正序。由於這類冒泡法只對前k+1個數據冒泡處置,所以我們稱它為——部分冒泡
願望本文所述對年夜家的java法式設計有所贊助。