一、冒泡排序有什么實際應用場景

1、數據庫查詢

冒泡排序可用于對數據庫中的數據進行排序，對于小規模數據集，冒泡排序的速度也足夠快。

2、數字圖像處理

冒泡排序可用于處理數字圖像中的像素點，比如對像素點的灰度值進行排序，從而得到更清晰、更準確的圖像。

3、傳感器數據采集

在傳感器采集的數據中，可能會出現一些異常點或者噪聲，使用冒泡排序可以將這些異常值篩選出來，并快速進行處理。

4、小規模數據排序

如，4個數進行排序時，通常手動寫6次比較的冒泡排序。

void cs(int &a, int &b) { // 對a和b進行比較、交換    if(a > b) {        int t = a;        a = b;        b = t;    }}// 調用cs(a, b);cs(b, c);cs(c, d);cs(a, b);cs(b, c);cs(a, b);

5、從高到低列隊

生活中，我們在集體活動中站隊時，名列前茅次站隊由于沒有固定的位置，往往是大家先隨便站成一排，然后再通過換位置的方式逐步形成高矮順序，這里主要是冒泡的思想。

二、冒泡排序（Bubble Sort）

1、基本思想

冒泡排序是一種交換排序，核心是冒泡，把數組中最小的那個往上冒，冒的過程就是和他相鄰的元素交換。

重復走訪要排序的數列，通過兩兩比較相鄰記錄的排序碼。排序過程中每次從后往前冒一個最小值，且每次能確定一個數在序列中的最終位置。若發生逆序，則交換；有倆種方式進行冒泡，一種是先把小的冒泡到前邊去，另一種是把大的元素冒泡到后邊。

趣味解釋：

有一群泡泡，其中一個泡泡跑到一個泡小妹說，小妹小妹你過來咱倆比比誰大，小妹說哇你好大，于是他跑到了泡小妹前面，又跟前面的一個泡大哥說，大哥，咱倆比比誰大唄。泡大哥看了他一眼他就老實了。這就是內層的for，那個泡泡跟每個人都比一次。

話說那個泡泡剛老實下來，另一個泡泡又開始跟別人比誰大了，這就是外層的for，每個泡泡都會做一次跟其他泡泡比個沒完的事。

2、實現邏輯

通過兩層循環控制：

3、性能分析

5、代碼實現

// 冒泡排序(C++)void bubble_sort(int arr[], int len)  {      int i, j;      for (i = 0; i < len; i++)          for (j = 1; j < len - i; j++)              if (arr[j - 1] > arr[j])                  swap(arr[j - 1], arr[j]);  }

6、優化改進

場景一：

在某次遍歷中如果沒有數據交換，說明整個數組已經有序。若初始序列就是排序好的，如果用基礎的冒泡排序方法，仍然還要比較O(N^2)次，但無交換次數。

改進思路：

通過設置標志位來記錄此次遍歷有無數據交換，進而可以判斷是否要繼續循環，設置一個flag標記，當在一趟序列中沒有發生交換，則該序列已排序好，但優化后排序的時間復雜度沒有發生量級的改變。

改進代碼：

// 冒泡排序改進(C++)void bubble_sort(int arr[], int len){    for (int i = 0; i < len-1; i++){        //比較n-1次        bool exchange = true;               //冒泡的改進，若在一趟中沒有發生逆序，則該序列已有序        for (int j = len-1; j >i; j--){     //每次從后邊冒出一個最小值            if (arr[j] < arr[j - 1]){       //發生逆序，則交換                swap(arr[j], arr[j - 1]);                exchange = false;            }        }        if (exchange){            return;        }    }}

場景二：

如果有100個數的數組，僅前面10個無序，后面90個都已排好序且都大于前面10個數字，那么在名列前茅趟遍歷后，最后發生交換的位置必定小于10，且這個位置之后的數據必定已經有序了。

改進思路：

記錄某次遍歷時最后發生數據交換的位置pos，這個位置之后的數據顯然已經有序了。因此通過記錄最后發生數據交換的位置就可以確定下次循環的范圍了。由于pos位置之后的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。

改進代碼：

// 冒泡排序改進void bubble_sort(int arr[], int len)  {      int j, k;      int flag;      flag = len;      while (flag > 0)      {          k = flag;          flag = 0;          for (j = 1; j < k; j++)              if (arr[j - 1] > arr[j])              {                  swap(arr[j - 1], arr[j]);                  flag = j;              }      }  }

延伸閱讀1：常用排序算法

上一篇

二叉樹解決了什么問題?

下一篇

ddl文件用什么軟件打開?