起泡排序又稱為冒泡排序。它是通過一系列的“交換”動作完成的。首先將第一和第二個記錄進行比較，如果第一個記錄大于第二個記錄，則兩者交換位置，否則保持原位置不變；然后比較第二和第三個記錄……一直按這種方式比較下去，最終最大的記錄被交換到最后，一趟冒泡排序完成。這個過程，大的記錄就像一塊石頭一樣“沉底”，小的記錄逐漸向上“浮動 ”，冒泡排序的名字也是由此而來的。

冒泡排序的步驟歸納如下(以升序排序為例)：

1、依次比較序列中相鄰的兩個元素 ，將較大的放在后面，這樣一趟下來 ，最大的元素就被放到了最后；
2、接著重復(fù)第一步，第二趟下來， 第二大的元素就被放到倒數(shù)第二的位 置上；
3、依次循環(huán)，直到最小的元素被放 在第一個位置上，排序結(jié)束。

冒泡排序基本算法實現(xiàn)如下：

//冒泡排序 void bubbleSort(int[] a, int n){int temp;for (int i = 0; i < n; i++) {for (int j = 1; j < n - i; j++) {if (a[j-1] > a[j]) {temp = a[j-1];a[j-1] = a[j];a[j] = temp;}}} }

java代碼實現(xiàn)如下：

public class BubbleSort {public static void main(String[] args) {int[] a = {2,5,9,3,0,4,6};bubbleSort(a,7);bubbleSortAdvanced(a,7);for (int i = 0; i < a.length; i++) {System. out.println(a[i]);}System. out.println("***********" );bubbleSortAdvanced(a,7);for (int i = 0; i < a.length; i++) {System. out.println(a[i]);}}//原始冒泡排序(注意n的取值)public static void bubbleSort(int[] a, int n){int temp;for (int i = 0; i < n; i++) {for (int j = 1; j < n - i; j++) {if (a[j-1] > a[j]) {temp = a[j-1];a[j-1] = a[j];a[j] = temp;}}}}/*** 冒泡排序優(yōu)化:** 設(shè)置一個標(biāo)志位flag，如果這一趟發(fā)生了交換，flag=true，否則flag=false。* 如果有一趟沒有發(fā)生交換，說明排序已經(jīng)完成。** 注意n的取值*/public static void bubbleSortAdvanced(int[] a, int n){int temp;boolean flag = true;while(flag){flag = false;for (int i = 0; i < n; i++) {for (int j = 1; j < n; j++) {if (a[j-1] > a[j]) {temp = a[j-1];a[j-1] = a[j];a[j] = temp;flag = true;//如果本趟沒有發(fā)生數(shù)據(jù)交換，說明排序已經(jīng)完成，不再進行比較}}}}} }

時間復(fù)雜度：

最壞情況下，待排序列逆序，此時對于外層循環(huán)的每次執(zhí)行，內(nèi)層循環(huán)中if語句的條件a[j-1] > a[j]始終成立，即基本操作執(zhí)行的次數(shù)為n-i。i的取值為1 ~ n-1。因此，基本操作總的執(zhí)行次數(shù)為(n-1+1)(n-1)/2=n(n-1)/2，由此可知時間復(fù)雜度為O(n2){n的平方}。

最好情況下，待排序列有序，此時內(nèi)層循環(huán)中if語句的條件始終不成立，交換不發(fā)生，且內(nèi)層循環(huán)執(zhí)行n-1次后整個算法結(jié)束，時間復(fù)雜度為O(n)。

綜上所述，冒泡排序的平均時間復(fù)雜度為O(n2){n的平方}。

---

空間復(fù)雜度：

由算法代碼可以看出，額外輔助空間只有一個temp，因此空間復(fù)雜度為0(1)。

總結(jié)

以上是生活随笔為你收集整理的【大话数据结构算法】冒泡排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。