一、冒泡排序介紹

　　冒泡排序（英語(yǔ)：Bubble Sort）是一種簡(jiǎn)單的排序算法。它重復(fù)地遍歷要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

二、冒泡排序原理

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2. 對(duì)每一對(duì)相鄰元素做同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這一步做完，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
   

三、冒泡排序圖解

四、冒泡排序總結(jié)

有N個(gè)數(shù)據(jù)需要比較N-1趟

每趟比較N-i次,i表示第幾趟，例如7個(gè)數(shù)據(jù)，第四趟需要比較 7-4 = 3次

五、冒泡排序python代碼實(shí)現(xiàn)

            
def bubble_sort(numlist):
 # 需要排列的數(shù)據(jù)個(gè)數(shù)
 N = len(numlist)
 # i 控制一共需要多少趟 N-1
 for i in range(N-1):
  # j 控制每趟需要比較多少次(因?yàn)閕是從0開(kāi)始，所以N-i-1)
  for j in range(N-i-1):
   # 判斷j和j+1兩個(gè)位置的數(shù)據(jù)大小
   if numlist[j]>numlist[j+1]:
    # 交換（交換的代碼有很多種寫(xiě)法）
    temp = numlist[j]
    numlist[j] = numlist[j+1]
    numlist[j+1] = temp
   
list = [19,2,13,8,34,25,7]
print("排序前l(fā)ist = %s"%list)
bubble_sort(list)
print("排序后list = %s"%list)
          

運(yùn)行結(jié)果為：

排序前l(fā)ist = [19, 2, 13, 8, 34, 25, 7]
排序后list = [2, 7, 8, 13, 19, 25, 34]

六、冒泡排序C語(yǔ)言代碼實(shí)現(xiàn)

            
#include 
            
              
// 創(chuàng)建一個(gè)冒泡函數(shù)，需要傳遞一個(gè)數(shù)組,和數(shù)組的長(zhǎng)度
void bubble_sort(int array[],int arrayLength)
{
 // i 控制一共需要循環(huán)多少趟，
 for (int i=0; i
              
                array[j+1])
   {
    //交換
    int temp = array[j];
    array[j] = array[j+1];
    array[j+1] = temp;
   }
  }
 }
}

int main(int argc, const char * argv[])
{
 // 函數(shù)的聲明
 void bubble_sort(int array[],int arrayLength);
 // 創(chuàng)建一個(gè)數(shù)組
 int numArray[] = {19,2,13,8,34,25,7};
 //進(jìn)行排序
 bubble_sort(numArray,7);
 
 printf("打印排序后的數(shù)組是：\n");
 for (int i=0; i<7; i++)
 {
  printf("%d ",numArray[i]);
 }
 return 0;
}
              
            
          

運(yùn)算結(jié)果為：

打印排序后的數(shù)組是：

2 7 8 13 19 25 34

七、冒泡排序的優(yōu)化

　　通過(guò)上面的案例我們已經(jīng)知道冒泡排序的原理和實(shí)現(xiàn)過(guò)程，但是在處理一些特殊數(shù)據(jù)上的時(shí)候，我們還可以對(duì)冒泡排序優(yōu)化，例如：一個(gè)數(shù)組本來(lái)就是有序，1，2，3，4，5，6，7，這樣的一個(gè)數(shù)組已經(jīng)是正確的順序的，我們只需要比較一趟后，發(fā)現(xiàn)這一趟所有的數(shù)據(jù)都沒(méi)有發(fā)生改變，就說(shuō)明這已經(jīng)是一個(gè)正確的順序的，后面的循環(huán)就沒(méi)必要循環(huán)下去了，這樣便能提高程序的效率，而我們只需要在冒泡排序的代碼中，判斷是否這一樣都沒(méi)發(fā)生交換即可。

python代碼實(shí)現(xiàn)如下：

            
def bubble_sort(numlist):
 # 需要排列的數(shù)據(jù)個(gè)數(shù)
 N = len(numlist)
 # i 控制一共需要多少趟 N-1
 for i in range(N-1):
  
  # 定義一個(gè)變量，用于記錄是否在本趟中發(fā)生了交換
  isChange = 0
  
  # j 控制每趟需要比較多少次(因?yàn)閕是從0開(kāi)始，所以N-i-1)
  for j in range(N-i-1):
   # 判斷j和j+1兩個(gè)位置的數(shù)據(jù)大小
   if numlist[j]>numlist[j+1]:
    # 交換（交換的代碼有很多種寫(xiě)法）
    temp = numlist[j]
    numlist[j] = numlist[j+1]
    numlist[j+1] = temp
    # 只要發(fā)生了交換，我們就改變isChange的值為1
    isChange = 1
  
  # 只要isChange =0說(shuō)明已經(jīng)是正確順序了，直接break即可
  if isChange == 0:
   break
   
list = [19,2,13,8,34,25,7]
print("排序前l(fā)ist = %s"%list)
bubble_sort(list)
print("排序后list = %s"%list)
          

運(yùn)行結(jié)果為：

排序前l(fā)ist = [19, 2, 13, 8, 34, 25, 7]
排序后list = [2, 7, 8, 13, 19, 25, 34]

C語(yǔ)言代碼實(shí)現(xiàn)如下：

            
#include 
            
              
// 創(chuàng)建一個(gè)冒泡函數(shù)，需要傳遞一個(gè)數(shù)組,和數(shù)組的長(zhǎng)度
void bubble_sort(int array[],int arrayLength)
{
 // i 控制一共需要循環(huán)多少趟，
 for (int i=0; i
              
                array[j+1])
   {
    //交換
    int temp = array[j];
    array[j] = array[j+1];
    array[j+1] = temp;
    // 只要發(fā)生了交換，我們就改變isChange的值為1
    isChange = 1;
   }
  }
  // 只要isChange =0說(shuō)明已經(jīng)是正確順序了，直接break即可
  if (isChange == 0)
  {
   break;
  }
 }
}

int main(int argc, const char * argv[])
{
 // 函數(shù)的聲明
 void bubble_sort(int array[],int arrayLength);
 // 創(chuàng)建一個(gè)數(shù)組
 int numArray[] = {19,2,13,8,34,25,7};
 //進(jìn)行排序
 bubble_sort(numArray,7);
 
 printf("打印排序后的數(shù)組是：\n");
 for (int i=0; i<7; i++)
 {
  printf("%d ",numArray[i]);
 }
 return 0;
}
              
            
          

運(yùn)行結(jié)果為：

打印排序后的數(shù)組是：

2 7 8 13 19 25 34

八、冒泡排序的時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度：O(n) （表示遍歷一次發(fā)現(xiàn)沒(méi)有任何可以交換的元素，排序結(jié)束。）
最壞時(shí)間復(fù)雜度：O(n2)

九、冒泡排序算法的穩(wěn)定性

　　冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，是不會(huì)再交換的；如果兩個(gè)相等的元素沒(méi)有相鄰，那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái)，這時(shí)候也不會(huì)交換，所以相同元素的前后順序并沒(méi)有改變，所以冒泡排序是一種穩(wěn)定排序算法。

侯哥語(yǔ)錄：我曾經(jīng)是一個(gè)職業(yè)教育者，現(xiàn)在是一個(gè)自由開(kāi)發(fā)者。我希望我的分享可以和更多人一起進(jìn)步。分享一段我喜歡的話給大家："我所理解的自由不是想干什么就干什么，而是想不干什么就不干什么。當(dāng)你還沒(méi)有能力說(shuō)不得時(shí)候，就努力讓自己變得強(qiáng)大，擁有說(shuō)不得權(quán)利。"

總結(jié)

以上所述是小編給大家介紹的python算法與數(shù)據(jù)結(jié)構(gòu)之冒泡排序?qū)嵗斀?，希望?duì)大家有所幫助，如果大家有任何疑問(wèn)歡迎給我留言，小編會(huì)及時(shí)回復(fù)大家的！