前言

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

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

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

從左到右，相鄰元素進(jìn)行比較。每次比較一輪，就會(huì)找到序列中大的一個(gè)或最小的一個(gè)。這個(gè)數(shù)就會(huì)從序列的最右邊冒出來。
以從小到大排序?yàn)槔谝惠啽容^后，所有數(shù)中大的那個(gè)數(shù)就會(huì)浮到最右邊；第二輪比較后，所有數(shù)中第二大的那個(gè)數(shù)就會(huì)浮到倒數(shù)第二個(gè)位置……就這樣一輪一輪地比較，最后實(shí)現(xiàn)從小到大排序。

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

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

冒泡排序過程細(xì)化

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

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

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}；此時(shí)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}；此時(shí)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]；也就是只剩下一個(gè)元素arr[0]；所以無需比較，產(chǎn)生的數(shù)組已經(jīng)升序有序

代碼描述

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

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

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

網(wǎng)站名稱：【數(shù)據(jù)結(jié)構(gòu)與算法——C語言版】5.排序算法（2）——冒泡排序-創(chuàng)新互聯(lián)
文章起源：http://jinyejixie.com/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)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)