Java實現冒泡排序與雙向冒泡排序算法的代碼示例

冒泡排序：
就是按索引逐次比較相鄰的兩個元素，如果大於/小於(取決於需要升序排還是降序排)，則置換，否則不做改變這樣一輪下來，比較了n-1次，n等於元素的個數；n-2, n-3 ... 一直到最後一輪，比較了1次所以比較次數為遞減：從n-1 到1
那麼總的比較次數為：1+2+3+...+(n-1), 以等差公式計算：(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5
用大O表示算法的時間複雜度：O(n^2) , 忽略了係數0.5和常數-n

 public class BubbleSort { public static void main(String[] args) { int len = 10; int[] ary = new int[len]; Random random = new Random(); for (int j = 0; j < len; j++) { ary[j] = random.nextInt(1000); } System.out.println("-------排序前------"); for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } /* * 升序， Asc1和Asc2優化了內部循環的比較次數，比較好* 總的比較次數： * Asc1、Asc2：(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> n*(n-1)/2 ==>(n^2-n)/2 * Asc： n^2-n */ // orderAsc(ary); // orderAsc2(ary); orderAsc1(ary); //降序，只需要把判斷大小於置換一下} static void orderAsc(int[] ary) { int count = 0;//比較次數int len = ary.length; for (int j = 0; j < len; j++) {//外層固定循環次數for (int k = 0; k < len - 1; k++) {//內層固定循環次數if (ary[k] > ary[k + 1]) { ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交換/* 交換兩個變量值* a=a+b * b=ab * a=ab */ } count++; } } System.out.println("/n-----orderAsc升序排序後------次數：" + count); for (int j = 0; j < len; j++) { System.out.print(ary[j] + " "); } } static void orderAsc1(int[] ary) { int count = 0;//比較次數int len = ary.length; for (int j = 0; j < len; j++) {//外層固定循環次數for (int k = len - 1; k > j; k--) {//內層從多到少遞減比較次數if (ary[k] < ary[k - 1]) { ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交換} count++; } } System.out.println("/n-----orderAsc1升序排序後------次數：" + count); for (int j = 0; j < len; j++) { System.out.print(ary[j] + " "); } } static void orderAsc2(int[] ary) { int count = 0;//比較次數int len = ary.length; for (int j = len - 1; j > 0; j--) {//外層固定循環次數/* * k < j; 總的比較次數=(n^2-n)/2 */ for (int k = 0; k < j; k++) {//內層從多到少遞減比較次數if (ary[k] > ary[k + 1]) { ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交換} count++; } } System.out.println("/n-----orderAsc2升序排序後------次數：" + count); for (int j = 0; j < len; j++) { System.out.print(ary[j] + " "); } } }

列印

-------排序前------ 898 7 862 286 879 660 433 724 316 737 -----orderAsc1升序排序後------次數：45 7 286 316 433 660 724 737 862 879 898

雙向冒泡排序
冒泡排序_雞尾酒排序、就是雙向冒泡排序。
此算法與冒泡排序的不同處在於排序時是以雙向在序列中進行排序,外層比較左右邊界l<r,
內層一個循環從左向右比，取高值置後；一個循環從右向左，取低值置前；
效率上，O(N^2), 不比普通的冒泡快

public class Bubble_CocktailSort { public static void main(String[] args) { int len = 10; int[] ary = new int[len]; Random random = new Random(); for (int j = 0; j < len; j++) { ary[j] = random.nextInt(1000); } /* * 交換次數最小也是1次，最大也是(n^2-n)/2次*/ // ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //測試交換次數// ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //測試交換次數System.out.println("-------排序前------"); for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } orderAsc1(ary); // orderAsc2(ary); //降序，只需要把判斷大小於置換一下} static void orderAsc1(int[] ary) { int compareCount = 0;//比較次數int changeCount = 0;//交換次數int len = ary.length; int left = 0, right = len -1, tl, tr; while (left < right) {//外層固定循環次數tl = left + 1; tr = right - 1; for (int k = left; k < right; k++) {//內層從多到少遞減比較次數, 從左向右if (ary[k] > ary[k + 1]) {//前大於後， 置換ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交換changeCount++; tr = k; //一輪中最後一比較的時候，將k所在索引賦給tr, tr表示以後比較的結束索引值, 從左向右比後，k表示左邊的索引} compareCount++; } right = tr; for (int k = right; k > left; k--) {//內層從多到少遞減比較次數, 從右向左if (ary[k] < ary[k - 1]) {//後小於前置換ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交換changeCount++; tl = k; //一輪中最後一比較的時候，將k所在索引賦給tl, tl表示以後比較的開始索引值, 從向右向左比後，k表示右邊的索引} compareCount++; } left = tl; } System.out.println("/n-----orderAsc1升序排序後------比較次數：" + compareCount + ", 交換次數：" + changeCount); for (int j = 0; j < len; j++) { System.out.print(ary[j] + " "); } } //跟orderAsc1的思路沒有區別static void orderAsc2(int[] ary) { int compareCount = 0;//比較次數int changeCount = 0;//交換次數int len = ary.length; int l = 0, r = len -1, tl, tr; for (; l < r; ) {//外層固定循環次數tl = l + 1; tr = r - 1; /* * 從左向右比，將大的移到後面*/ for (int k = l; k < r; k++) { if (ary[k] > ary[k + 1]) { int temp = ary[k] + ary[k + 1]; ary[k + 1] = temp - ary[k + 1]; ary[k] = temp - ary[k + 1]; changeCount++; tr = k; } compareCount++; } r = tr; /* * 從右向左比，將小的移到前面*/ for (int k = r; k > l; k--) { if (ary[k] < ary[k - 1]) { int temp = ary[k] + ary[k - 1]; ary[k - 1] = temp - ary[k - 1]; ary[k] = temp - ary[k - 1]; changeCount++; tl = k; } compareCount++; } l = tl; } System.out.println("/n-----orderAsc2升序排序後------比較次數：" + compareCount + ", 交換次數：" + changeCount); for (int j = 0; j < len; j++) { System.out.print(ary[j] + " "); } } }

列印

-------排序前------ 783 173 53 955 697 839 201 899 680 677 -----orderAsc1升序排序後------比較次數：34, 交換次數：22 53 173 201 677 680 697 783 839 899 955