【數(shù)據(jù)結(jié)構(gòu)與算法——C語言版】5.排序算法（2）——冒泡排序-創(chuàng)新互聯(lián)

前言

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

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

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

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

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

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

冒泡排序過程細化

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

數(shù)組arr[5] = {5,1,4,2,8}，如果采用冒泡排序?qū)ζ溥M行升序（由小到大）排序，則整個排序過程如下所示：

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

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

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

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

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

代碼描述

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

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

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

網(wǎng)站名稱：【數(shù)據(jù)結(jié)構(gòu)與算法——C語言版】5.排序算法（2）——冒泡排序-創(chuàng)新互聯(lián)
文章起源：http://muchs.cn/article36/dcphpg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、關(guān)鍵詞優(yōu)化、企業(yè)網(wǎng)站制作、網(wǎng)站建設(shè)、服務(wù)器托管、網(wǎng)站改版

廣告

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