冒泡排序

1. 思想

　　冒泡排序（Bubble Sort）是一種交換排序，基本思路是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。

?

2. 實現

2.1 初學常用的一種

public static <T extends Comparable<? super T>> void BubbleSort(T[] a) {int length = a.length;for (int i = 0; i < length; i++) {for (int j = i+1; j < length; j++) {if (a[i].compareTo(a[j]) > 0) {Object obj = a[i];a[j] = a[i];a[i] = (T)obj;} // end if} // end for} // end for } // end BubbleSort

　　缺陷：每一次內循環結束時，對其余的關鍵字沒有幫助，甚至把原來靠近正確排序位置的記錄交換到較遠的地方。即，算法是低效的。

?

?

2.2 正宗的冒泡排序

public static <T extends Comparable<? super T>> void BubbleSort(T[] a) {int length = a.length;for (int i = 0; i < length - 1; i++) {for (int j = length - 2; j >= i; j--) {if (a[j].compareTo(a[j+1]) > 0) {Object obj = a[i];a[i] = a[j];a[j] = (T)obj;} // end if} // end for} // end for } // end BubbleSort

　　

　　顯然這一算法比之前的實現要有效，圖中較小的數字如同氣泡慢慢浮到上面，因此將此算法命名為冒泡排序。?

?

2.3 冒泡排序的優化

　　對于已經有序或接近有序的集合時，會進行很多次不必要的循環比較，為此，需要改進實現，設置一個flag記錄在一次循環比較中是否有交換操作，如果沒有說明集合已經有序。

public static <T extends Comparable<? super T>> void BubbleSort(T[] a) {int length = a.length;boolean flag = true; // 用flag作為標記for (int i = 0; (i < length - 1) && flag; i++) {flag = false;for (int j = length - 2; j >= i; j--) {if (a[j].compareTo(a[j+1]) > 0) {Object obj = a[i];a[i] = a[j];a[j] = (T)obj;flag = true; // 有數據交換則為true} // end if} // end for} // end for } // end BubbleSort

?

2.4 冒泡排序復雜度分析

　　最好的情況下，也就是數組有序時，根據最后改進的代碼，需要比較n-1次關鍵字，沒有數據交換，時間復雜度為O(n)。最壞的情況下，即待排序記錄全為倒序，此時比較1+2+3+4+…+(n-1)?= n(n-1)/2次，并作等數量級的記錄移動。所以時間復雜度為O(n²)。

?

簡單選擇排序

1. 思想

　　冒泡排序的思想就不斷地在交換，通過交換完成最終的排序。這種方式太繁瑣，可不可以在確定位置的時候在交換，減少交換操作，完成只交換一次就完成相應關鍵字的排序定位？這就是選擇排序的初步思想。

?

2. 排序算法

　　簡單選擇排序（Simple Selection Sort）就是通過n-i次關鍵字間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，并和第i（1 ≤ i ≤ n）個記錄交換。

// simple selection sort public static <T extends Comparable<? super T>> void SelectSort(T[] a) {int length = a.length;for (int i = 0; i < length - 1; i++) {int min = i;for (int j = i+1; j < length; j++) {if (a[min].compareTo(a[j]) > 0) {min = j;} // end if} // end forif (i != min) {Object obj = a[min];a[min] = a[i];a[i] = (T)obj;} // end if} // end for } // end SelectSort

?

3. 簡單選擇排序復雜度分析

　　從簡單選擇排序過程看，最大的特點是減少了移動數據的次數，這樣節約了時間。無論最好還是最差的情況下，比較次數都是一樣的，第i趟要比較n-i次關鍵字，共需要比較(n-1)+(n-2)+…+2+1=n(n-1)/2次，最好情況下，即有序時，交換0次，最壞情況下，即逆序時，交換n-1次。最終排序時間為比較和移動的總和，時間復雜度為O(n²)。

盡管與冒泡排序同為O(n²)，但簡單選擇排序的性能還是要略優于冒泡排序。（下列比較缺不是！）

?

冒泡與選擇排序對比

import java.util.Arrays; /*** sort for Array* @author Administrator*/ public class Sort {// 非標準的冒泡排序，最簡單的交換排序！（讓每一個關鍵字，都和它后面的每一個關鍵字比較，如果大則交換）public static void BubbleSort1(int[] a) {int length = a.length;for (int i = 0; i < length; i++) {for (int j = i+1; j < length; j++) {if (a[i] > a[j]) {int obj = a[i];a[i] = a[j];a[j] = obj;} // end if} // end for} // end for} // end BubbleSort// 標準冒泡排序public static void BubbleSort2(int[] a) {int length = a.length;for (int i = 0; i < length - 1; i++) {for (int j = length - 2; j >= i; j--) {if (a[j] > a[j+1]) {int obj = a[j];a[j] = a[j+1];a[j+1] = obj;} // end if} // end for} // end for} // end BubbleSortpublic static void BubbleSort3(int[] a) {int length = a.length;boolean flag = true; // 用flag作為標記for (int i = 0; (i < length - 1) && flag; i++) {flag = false;for (int j = length - 2; j >= i; j--) {if (a[j] > a[j+1]) {int obj = a[j];a[j] = a[j+1];a[j+1] = obj;flag = true; // 有數據交換則為true} // end if} // end for} // end for} // end BubbleSort// simple selection sortpublic static void SelectSort(int[] a) {int length = a.length;for (int i = 0; i < length - 1; i++) {int min = i;for (int j = i+1; j < length; j++) {if (a[min] > a[j]) {min = j;} // end if} // end forif (i != min) {int obj = a[min];a[min] = a[i];a[i] = obj;} // end if} // end for} // end SelectSortpublic static void main(String[] args) {// 隨機生成50000、50_0000的整數int[] a = new int[50_0000];for (int i = 0; i < a.length; i++) {a[i] = (int)(Math.random() * 500);//System.out.print(a[i] + " ");}// System.out.println();// 保證各個排序算法使用的數據一樣int[] a2 = Arrays.copyOf(a, a.length);int[] a3 = Arrays.copyOf(a, a.length);int[] a4 = Arrays.copyOf(a, a.length);
Date d1 = new Date();BubbleSort1(a); // 最常用的初學實現 50000:919，962，1032 500000：59425，60701，59811System.out.println(new Date().getTime() - d1.getTime());Date d2 = new Date();BubbleSort2(a2); // 標準冒泡 50000:5332，5300，5957 500000：491104，480838，478621System.out.println(new Date().getTime() - d2.getTime());Date d3 = new Date();BubbleSort3(a3); // 改進冒泡 50000: 5477，5648，5696 500000：526451，522458,503981System.out.println(new Date().getTime() - d3.getTime());Date d4 = new Date();SelectSort(a4); // 50000: 1118，1256，1076 500000：107144，95680,94796System.out.println(new Date().getTime() - d4.getTime());} } // end Sort

　　可以看出對于隨機數組，常用的冒泡性能最好，接下來是簡單選擇排序，標準冒泡和改進的冒泡效率不如初學常用的冒泡高。改進的冒泡排序適合于接近有序或已經有序的情況。

轉載于:https://www.cnblogs.com/datamining-bio/p/9715774.html

總結

以上是生活随笔為你收集整理的1. 冒泡与选择排序及其比较的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。