冒泡法排序

冒泡排序法是什么

冒泡排序的英文Bubble Sort，是一種最基礎(chǔ)的交換排序。

　　大家一定都喝過汽水，汽水中常常有許多小小的氣泡，嘩啦嘩啦飄到上面來。這是因?yàn)榻M成小氣泡的二氧化碳比水要輕，所以小氣泡可以一點(diǎn)一點(diǎn)向上浮動(dòng)。而我們的冒泡排序之所以叫做冒泡排序，正是因?yàn)檫@種排序算法的每一個(gè)元素都可以像小氣泡一樣，根據(jù)自身大小，一點(diǎn)一點(diǎn)向著數(shù)組的一側(cè)移動(dòng)。

冒泡排序算法的原理如下：

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

具體如何來移動(dòng)呢？讓我們來看一個(gè)栗子：

請(qǐng)點(diǎn)擊輸入圖片描述

有8個(gè)數(shù)組成一個(gè)無序數(shù)列：5，8，6，3，9，2，1，7，希望從小到大排序。按照冒泡排序的思想，我們要把相鄰的元素兩兩比較，根據(jù)大小來交換元素的位置，過程如下：

首先讓5和8比較，發(fā)現(xiàn)5比8要小，因此元素位置不變。

接下來讓8和6比較，發(fā)現(xiàn)8比6要大，所以8和6交換位置。

請(qǐng)點(diǎn)擊輸入圖片描述

請(qǐng)點(diǎn)擊輸入圖片描述

繼續(xù)讓8和3比較，發(fā)現(xiàn)8比3要大，所以8和3交換位置。

請(qǐng)點(diǎn)擊輸入圖片描述

請(qǐng)點(diǎn)擊輸入圖片描述

繼續(xù)讓8和9比較，發(fā)現(xiàn)8比9要小，所以元素位置不變。

接下來讓9和2比較，發(fā)現(xiàn)9比2要大，所以9和2交換位置。

請(qǐng)點(diǎn)擊輸入圖片描述

請(qǐng)點(diǎn)擊輸入圖片描述

接下來讓9和1比較，發(fā)現(xiàn)9比1要大，所以9和1交換位置。

請(qǐng)點(diǎn)擊輸入圖片描述

請(qǐng)點(diǎn)擊輸入圖片描述

最后讓9和7比較，發(fā)現(xiàn)9比7要大，所以9和7交換位置。

請(qǐng)點(diǎn)擊輸入圖片描述

請(qǐng)點(diǎn)擊輸入圖片描述

這樣一來，元素9作為數(shù)列的最大元素，就像是汽水里的小氣泡一樣漂啊漂，漂到了最右側(cè)。

這時(shí)候，我們的冒泡排序的第一輪結(jié)束了。數(shù)列最右側(cè)的元素9可以認(rèn)為是一個(gè)有序區(qū)域，有序區(qū)域目前只有一個(gè)元素。

請(qǐng)點(diǎn)擊輸入圖片描述

下面，讓我們來進(jìn)行第二輪排序：

首先讓5和6比較，發(fā)現(xiàn)5比6要小，因此元素位置不變。

接下來讓6和3比較，發(fā)現(xiàn)6比3要大，所以6和3交換位置。

請(qǐng)點(diǎn)擊輸入圖片描述

請(qǐng)點(diǎn)擊輸入圖片描述

繼續(xù)讓6和8比較，發(fā)現(xiàn)6比8要小，因此元素位置不變。

接下來讓8和2比較，發(fā)現(xiàn)8比2要大，所以8和2交換位置。

請(qǐng)點(diǎn)擊輸入圖片描述

接下來讓8和1比較，發(fā)現(xiàn)8比1要大，所以8和1交換位置。

請(qǐng)點(diǎn)擊輸入圖片描述

請(qǐng)點(diǎn)擊輸入圖片描述

繼續(xù)讓8和7比較，發(fā)現(xiàn)8比7要大，所以8和7交換位置。

請(qǐng)點(diǎn)擊輸入圖片描述

請(qǐng)點(diǎn)擊輸入圖片描述

第二輪排序結(jié)束后，我們數(shù)列右側(cè)的有序區(qū)有了兩個(gè)元素，順序如下：

請(qǐng)點(diǎn)擊輸入圖片描述

至于后續(xù)的交換細(xì)節(jié)，我們這里就不詳細(xì)描述了，第三輪過后的狀態(tài)如下：

請(qǐng)點(diǎn)擊輸入圖片描述

第四輪過后狀態(tài)如下：

請(qǐng)點(diǎn)擊輸入圖片描述

第五輪過后狀態(tài)如下：

請(qǐng)點(diǎn)擊輸入圖片描述

第六輪過后狀態(tài)如下：

請(qǐng)點(diǎn)擊輸入圖片描述

第七輪過后狀態(tài)如下（已經(jīng)是有序了，所以沒有改變）：

請(qǐng)點(diǎn)擊輸入圖片描述

第八輪過后狀態(tài)如下（同樣沒有改變）：

請(qǐng)點(diǎn)擊輸入圖片描述

到此為止，所有元素都是有序的了，這就是冒泡排序的整體思路。

原始的冒泡排序是穩(wěn)定排序。由于該排序算法的每一輪要遍歷所有元素，輪轉(zhuǎn)的次數(shù)和元素?cái)?shù)量相當(dāng)，所以時(shí)間復(fù)雜度是O（N^2） 。

冒泡排序代碼

希望對(duì)您有所幫助！~

冒泡排序法

方法一：每趟從第一個(gè)元素開始，依次與下一個(gè)元素比較，大的往下交換;

方法二：記錄交換位置，可以省略下趟不必要的比較（如果后面幾個(gè)元素已經(jīng)是有序的，第二趟就直接不用比較這幾個(gè)元素）;

方法三：雙向冒泡，正向找最大(從最小元素交換位置處開始比較，找到最大元素并記錄交換位置)，反向找最小(從最大元素交換位置處開始比較，找到最小元素并記錄交換位

冒泡排序是比較基礎(chǔ)的排序算法之一，其思想是相鄰的元素兩兩比較，較大的數(shù)下沉，較小的數(shù)冒起來，這樣一趟比較下來，最大(小)值就會(huì)排列在一端，整個(gè)過程如同氣泡冒起，因此被稱作冒泡排序。

冒泡排序法是什么

冒泡排序，是指計(jì)算機(jī)的一種排序方法，它的時(shí)間復(fù)雜度為O（n^2），雖然不及堆排序、快速排序的O（nlogn，底數(shù)為2），但是有兩個(gè)優(yōu)點(diǎn)：1.“編程復(fù)雜度”很低，很容易寫出代碼；2.具有穩(wěn)定性，這里的穩(wěn)定性是指原序列中相同元素的相對(duì)順序仍然保持到排序后的序列，而堆排序、快速排序均不具有穩(wěn)定性。不過，一路、二路歸并排序、不平衡二叉樹排序的速度均比冒泡排序快，且具有穩(wěn)定性，但速度不及堆排序、快速排序。冒泡排序是經(jīng)過n-1趟子排序完成的，第i趟子排序從第1個(gè)數(shù)至第n-i個(gè)數(shù)，若第i個(gè)數(shù)比后一個(gè)數(shù)大（則升序，小則降序）則交換兩數(shù)

冒泡排序法，思路詳解

冒泡排序是最簡(jiǎn)單的排序方法，理解起來容易。雖然它的計(jì)算步驟比較多，不是最快的，但它是最基本的，初學(xué)者一定要掌握。

冒泡排序的原理是：從左到右，相鄰元素進(jìn)行比較。每次比較一輪，就會(huì)找到序列中最大的一個(gè)或最小的一個(gè)。這個(gè)數(shù)就會(huì)從序列的最右邊冒出來。

以從小到大排序?yàn)槔谝惠啽容^后，所有數(shù)中最大的那個(gè)數(shù)就會(huì)浮到最右邊；第二輪比較后，所有數(shù)中第二大的那個(gè)數(shù)就會(huì)浮到倒數(shù)第二個(gè)位置……就這樣一輪一輪地比較，最后實(shí)現(xiàn)從小到大排序。

比如對(duì)下面這個(gè)序列進(jìn)行從小到大排序：
90 21 132 -58 34

第一輪：

比較時(shí)，每輪中第 n 次比較是新序列中第 n 個(gè)元素和第 n+1 個(gè)元素的比較（假如 n 從 1 開始）。

第二輪：

第三輪：

到此第三輪就比較完了。第三輪的結(jié)果是找到了序列中第三大的那個(gè)數(shù)，并浮到了最右邊第三個(gè)位置。

第四輪：

從這個(gè)例子中還可以總結(jié)出，如果有 n 個(gè)數(shù)據(jù)，那么只需要比較 n–1 輪，因?yàn)槊窟M(jìn)行一輪排序，就能找到一個(gè)最大的數(shù)字，所以每輪比較進(jìn)行n-1-i次（i為右邊已經(jīng)確定位置的數(shù)字個(gè)數(shù)，也就是已經(jīng)進(jìn)行的輪數(shù)）。

下面寫一個(gè)程序：

輸出結(jié)果為：0 1 2 3 4 5 6 7 8 9

什么是冒泡排序法？

冒泡排序（BubbleSort）的基本概念是：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序。

C語言冒泡排序法是什么？

冒泡排序法，是C語言常用的排序算法之一，意思是對(duì)一組數(shù)字進(jìn)行從大到小或者從小到大排序的一種算法。

具體方法是：

相鄰數(shù)值兩兩交換。從第一個(gè)數(shù)值開始，如果相鄰兩個(gè)數(shù)的排列順序與我們的期望不同，則將兩個(gè)數(shù)的位置進(jìn)行交換（對(duì)調(diào)）；如果其與我們的期望一致，則不用交換。重復(fù)這樣的過程，一直到最后沒有數(shù)值需要交換，則排序完成。

C語言常見的排序算法：

1、冒泡排序

基本思想：比較相鄰的兩個(gè)數(shù)，如果前者比后者大，則進(jìn)行交換。每一輪排序結(jié)束，選出一個(gè)未排序中最大的數(shù)放到數(shù)組后面。

2、快速排序

基本思想:選取一個(gè)基準(zhǔn)元素，通常為數(shù)組最后一個(gè)元素（或者第一個(gè)元素）。從前向后遍歷數(shù)組，當(dāng)遇到小于基準(zhǔn)元素的元素時(shí)，把它和左邊第一個(gè)大于基準(zhǔn)元素的元素進(jìn)行交換。在利用分治策略從已經(jīng)分好的兩組中分別進(jìn)行以上步驟，直到排序完成。

3、直接插入排序

基本思想：和交換排序不同的是它不用進(jìn)行交換操作，而是用一個(gè)臨時(shí)變量存儲(chǔ)當(dāng)前值。當(dāng)前面的元素比后面大時(shí)，先把后面的元素存入臨時(shí)變量，前面元素的值放到后面元素位置，再到最后把其值插入到合適的數(shù)組位置。

4、直接選擇排序

基本思想：依次選出數(shù)組最小的數(shù)放到數(shù)組的前面。首先從數(shù)組的第二個(gè)元素開始往后遍歷，找出最小的數(shù)放到第一個(gè)位置。再從剩下數(shù)組中找出最小的數(shù)放到第二個(gè)位置。以此類推，直到數(shù)組有序。

以上內(nèi)容參考 百度百科-排序算法、百度百科-c語言冒泡排序