?前言?：
演算法是一個程式員的內功，能很好的體現程式員的編程思維，通過學習和掌握常見的演算法，不僅能提高coding能力，還能更加容易在筆面試中脫穎而出，本專欄將記錄博主刷演算法題的程序，不定期的會更新一些優質的演算法題，如果對大家有幫助，別忘了三連支持喲！
目錄
?前言?：
?冒泡排序的思想?
💎具體思路形象化比喻💎
💎冒泡排序的圖解💎
?具體代碼展示?
?時間復雜度的計算?
?冒泡排序的思想?
冒泡排序可以說是排序演算法中最基礎，最簡單的，但是它的比較與交換思想確是十分值得借鑒的，
💎具體思路形象化比喻💎
💡：當我們要把10個數字進行冒泡排序時，我們可以這樣思考該問題，把問題轉化為有10個人來比武，我們該如何確定其武力的高低呢？我們可以采用打擂臺的方法（為了方便描述問題，給這10個人編號為0至9），我們先假設0號武力最強，讓他當擂主守擂，然后1~9號不服，因此我們讓1~9號依次上擂臺比武，若0號贏了說明其有實力，讓他繼續打后面的人，若輸了則代表0號沒有實力，則讓贏的人當擂主繼續接受后面人的挑戰，這樣下來最后站在擂臺上的一定是所有人中實力最強的，則給他第一名的獎牌，讓他去觀戰，然后我們重復該思路在剩余9個人中，決出最強者，拿到第二名的獎牌，以此類推，當第九輪時我們將發放第九名的獎牌，這時1~9名都已經確定了，那么剩下的那個人一定是第十名，所以我們有這樣的規律，n個人比武我們最多比n-1輪，
💡： 讀到這里大家可能還有疑惑為什么n個人最多是n-1輪呢？少于n-1輪的情況是怎么出現的？這個問題先放在這里，等看完圖解后相信大家會明白很多，
💎冒泡排序的圖解💎
🔑：圖例：（該圖片轉載至網路圖庫）
從之前的講述中我們由打擂思想可以知道每一趟比較都會把最大值放到最右邊，從這個圖中我們可以看到先假設第一個數最大，然后讓它和后面的一個數比較，如果大就交換位置，如果小了，就讓大的那個代替它去爭最大值，繼續往后比較，而且由圖可知每一次比較都是相鄰元素進行比較，并且保證每一次相鄰元素的右邊那個必定是較大的數，
至于為什么n個數最多是n-1次，這種最多的情況是在每一個元素都錯位的基礎上（意思是每一個元素在一開始的位置和最終有序的位置不一致，即目標升序，開始降序），那么我們就要在0~n-1范圍上通過上述方法把最大值放在n-1位置上，再在0~n-2范圍上重復該操作，依次類推，因為所有數都是錯位的所以每一次比較都是必要的，那每一次操作均不可以少，所以是n-1次，
如果我們假設10個數中有5個數的位置開始就已經正確了，所以我們只需要在剩下的5個數中進行上述思想把最大值放到這5個錯位的位置的最右邊，這樣只要4次就足夠讓這10個數有序，
所以我們可以總結出以下規律，n個數最多進行n-1趟，實際進行次數是（錯位數的數目-1）.
?具體代碼展示?
void Swap(int arr[], int i, int j)
{
//交換法1
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
//交換法2
//arr[i] = arr[i] ^ arr[j];
//arr[j] = arr[i] ^ arr[j];
//arr[j] = arr[i] ^ arr[j];
}
void bubuleSort(int arr[], int sz)
{
for (int i = sz - 1; i > 0; i--)
{
int flag = 0;//假設每一趟進來時都沒有排序完
for (int j = 0; j < i; j++)
{
if (arr[j] > arr[j + 1])
{
flag = 1;
Swap(arr,j,j+1);//冒泡排序本質是相鄰元素比較大的向右送
}
}
if (flag == 0)//如果一次過后flag=0說明這一趟沒有交換，所有數已經拍好序
{
break;
}
}
}?時間復雜度的計算?
以上代碼，還可做優化在此僅作參考，若有更好的演算法，還望能夠私信告知，多謝各位，
由于本人水平十分有限，若有錯誤請即使告知！如果有幫助別忘了，萬分感謝，
點贊👍 收藏? 關注?
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297835.html
標籤：其他
上一篇：【資料結構】二叉樹之堆的實作
下一篇：【演算法訓練營】(day2)