【數據結構與算法——C語言版】5.排序算法（2）——冒泡排序-創新互聯

前言

上篇文章【數據結構與算法——C語言版】4. 排序算法（1）——選擇排序我們介紹了排序算法中的選擇排序，其時間復雜度是O(n²)，本篇文章我們將介紹另一種同樣時間復雜度是O(n²)的排序算法——冒牌排序，這兩種算法思路不同，但都是兩層循環，實用性不高，但有必要通過講解來掌握不同的算法思路。

創新互聯公司是一家集網站建設,樂山企業網站建設,樂山品牌網站建設,網站定制,樂山網站建設報價,網絡營銷,網絡優化,樂山網站推廣為一體的創新建站企業，幫助傳統企業提升企業形象加強企業競爭力。可充分滿足這一群體相比中小企業更為豐富、高端、多元的互聯網需求。同時我們時刻保持專業、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們為更多的企業打造出實用型網站。冒泡排序核心思想

選擇排序的核心思想是每次找到最小值并與第i個元素交換，找n次。
而冒泡排序的核心思想是每次遍歷整個數組，比較相鄰的兩個元素arr[i]和arr[j]，將較大者放在arr[j]的位置，然后繼續比較arr[j]和arr[j+1]；將數組遍歷n次后（n為數組元素個數），數組升序有序。
該算法能使數組有序的核心原因如下：

從左到右，相鄰元素進行比較。每次比較一輪，就會找到序列中大的一個或最小的一個。這個數就會從序列的最右邊冒出來。
以從小到大排序為例，第一輪比較后，所有數中大的那個數就會浮到最右邊；第二輪比較后，所有數中第二大的那個數就會浮到倒數第二個位置……就這樣一輪一輪地比較，最后實現從小到大排序。

用一張圖片直觀的觀察一下：

第一輪遍歷中，總是選擇大的那個數并交換至靠右的位置，第一輪比較完成后，數組中大的元素50就被“冒”到了右邊
最后一輪遍歷，arr[0]就是最小的元素2，所以最后一輪遍歷沒有發生交換，即數組已升序有序。

冒泡排序過程細化

我們還是用一個例子，一步步帶著大家來理解冒泡排序的過程。

數組arr[5] = {5,1,4,2,8}，如果采用冒泡排序對其進行升序（由小到大）排序，則整個排序過程如下所示：

1. 第一次遍歷數組arr，兩兩比較arr[i]和arr[i+1]，并將較大者交換到arr[i+1]。第一次遍歷前，數組arr[5] = {5,1,4,2,8}；遍歷后，數組arr[5] = {1,4,2,5,8}；此時arr[4]已經是大值8，所以下次遍歷我們只需要遍歷arr[0 ~ 3]
   

2. 第二次遍歷數組arr，兩兩比較arr[i]和arr[i+1]，并將較大者交換到arr[i+1]。第一次遍歷前，數組arr[5] = {1,4,2,5,8}；遍歷后，數組arr[5] = {1,2,4,5,8}；此時arr[3]已經是次大值5，且arr[3~4]保持升序有序；所以下次遍歷我們只需要遍歷arr[0 ~ 2]；
   

3. 第三次遍歷數組arr，兩兩比較arr[i]和arr[i+1]，并將較大者交換到arr[i+1]。第一次遍歷前，數組arr[5] = {1,2,4,5,8}；遍歷后，數組arr[5] = {1,2,4,5,8}

4. 第四次遍歷數組arr，兩兩比較arr[i]和arr[i+1]，并將較大者交換到arr[i+1]。第一次遍歷前，數組arr[5] = {1,2,4,5,8}；遍歷后，數組arr[5] = {1,2,4,5,8}

5. 第五次遍歷數組arr，這次我們只需要遍歷 arr[0~0]；也就是只剩下一個元素arr[0]；所以無需比較，產生的數組已經升序有序

代碼描述

void bubbleSort(int arr[], int size)
{for (int i = 0; i< size; i++) // 可優化點1
	{int count = 0;
		for (int j = 0; j< size - i; j++)	// 每次遍歷都會產生一個較大值放到后面，所以第i遍歷就只需要比較size - i個元素
		{	if (arr[j] >arr[j+1])//這是升序排法，前一個數和后一個數比較，如果前數大則與后一個數換位置
			{		int tem = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tem;
				count = 1;
			}
		}
		if (count == 0) {// 優化點2：如果某一趟沒有交換位置，則說明已經排好序，直接退出循環
			break;
		}
	}
}

注釋的位置指出了兩個優化點
第一個優化點，我們可以修改為for (int i = 0; i< size - 1; i++)通過上面的圖描述，也可以看出實際上n個元素的數組，我們只需要遍歷n-1次，第n次遍歷時數組只剩下第一個元素“需要”比較，只有一個元素所以可省去多出來的一次循環
第二個優化點，其實已經寫出來了，每次遍歷比較前，用count記錄交換的次數，如果某趟沒有發生交換，說明此時數組已經有序，可以直接退出循環
其中，第一個優化點不建議，因為優化跟沒優化是一樣的，寫上size - 1反倒會造成一些誤導（因為數組遍歷一般都是[0~size)）
第二個優化點可以加上，如果待排序數組是{1,2,3,5,4}，這樣我們只需要執行一次遍歷，節省了很多時間

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站名稱：【數據結構與算法——C語言版】5.排序算法（2）——冒泡排序-創新互聯
文章起源：http://m.kartarina.com/article36/dcphpg.html

成都網站建設公司_創新互聯，為您提供商城網站、關鍵詞優化、企業網站制作、網站建設、服務器托管、網站改版

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯