冒泡排序演算法實驗心得

⑴ 冒泡排序與選擇排序的比較（python實現）

通過學習排序演算法，發現冒泡排序和選擇排序在演算法實現上，十分的近似，下面進行必要的一些講解：

讓數組當中相鄰的兩個數進行比較， 數組當中比較小的數值向下沉，數值比較大的向上浮！外層for循環控制循環次數，內層for循環控制相鄰的兩個元素進行比較。

將一個序列分為兩部分， 前面是有序序列，後面是無序序列，不斷的將後面的無序序列中的最小值添加到前面的有序序列中，直到後面的無序序列中沒有值,開始的時候將第一個值作為有序序列。

由於冒泡排序中元素需要兩兩比較，所以要 遍歷 所有元素， 冒牌排序演算法，非常適用於尋找列表中最大值或者，最小值 。

在選擇排序中，我們也需要一輪輪的選出剩餘的無需元素中的最小值，所以也要一次次的遍歷無序列表， 非常契合的使用冒泡的思想去選出最小值 。

【結論】：看這兩個演算法其實思維不同，但是實現的編碼過程十分一致。如果看程序看蒙了，其實也不要緊，思維上能明白兩者的區別就行...

⑵ 璋佽兘璁蹭竴涓嬪啋娉℃帓搴忓師鐞

鍐掓場鎺掑簭綆楁硶鐨勫師鐞嗗備笅錛

1錛屾瘮杈冪浉閭葷殑鍏冪礌銆傚傛灉絎涓涓姣旂浜屼釜澶э紝灝變氦鎹浠栦滑涓や釜銆

2錛屽規瘡涓瀵圭浉閭誨厓緔犲仛鍚屾牱鐨勫伐浣滐紝浠庡紑濮嬬涓瀵瑰埌緇撳熬鐨勬渶鍚庝竴瀵廣傚湪榪欎竴鐐癸紝鏈鍚庣殑鍏冪礌搴旇ヤ細鏄鏈澶х殑鏁般

3錛岄拡瀵規墍鏈夌殑鍏冪礌閲嶅嶄互涓婄殑姝ラわ紝闄や簡鏈鍚庝竴涓銆

4錛屾寔緇姣忔″硅秺鏉ヨ秺灝戠殑鍏冪礌閲嶅嶄笂闈㈢殑姝ラわ紝鐩村埌娌℃湁浠諱綍涓瀵規暟瀛楅渶瑕佹瘮杈冦

銆

2錛岀畻娉曠ǔ瀹氭э細

鍐掓場鎺掑簭灝辨槸鎶婂皬鐨勫厓緔犲線鍓嶈皟鎴栬呮妸澶х殑鍏冪礌寰鍚庤皟銆傛瘮杈冩槸鐩擱偦鐨勪袱涓鍏冪礌姣旇緝錛屼氦鎹涔熷彂鐢熷湪榪欎袱涓鍏冪礌涔嬮棿銆

鎵浠ワ紝濡傛灉涓や釜鍏冪礌鐩哥瓑錛屾槸涓嶄細鍐嶄氦鎹㈢殑錛涘傛灉涓や釜鐩哥瓑鐨勫厓緔犳病鏈夌浉閭伙紝閭ｄ箞鍗充嬌閫氳繃鍓嶉潰鐨勪袱涓や氦鎹㈡妸涓や釜鐩擱偦璧鋒潵錛岃繖鏃跺欎篃涓嶄細浜ゆ崲錛屾墍浠ョ浉鍚屽厓緔犵殑鍓嶅悗欏哄簭騫舵病鏈夋敼鍙橈紝鎵浠ュ啋娉℃帓搴忔槸涓縐嶇ǔ瀹氭帓搴忕畻娉曘

鍙傝冭祫鏂欙細鐧懼害鐧劇----鍐掓場鎺掑簭

⑶ 鍐掓場鎺掑簭鐨勪腑蹇冩濇兂鏄浠涔堬紵

鍐掓場鎺掑簭鐨勪腑蹇冩濇兂鏄錛氫粠鏃犲簭搴忓垪澶撮儴寮濮嬶紝榪涜屼袱涓ゆ瘮杈冿紝鏍規嵁澶у皬浜ゆ崲浣嶇疆錛岀洿鍒版渶鍚庡皢鏈澶э紙灝忥級鐨勬暟鎹鍏冪礌浜ゆ崲鍒頒簡鏃犲簭闃熷垪鐨勯槦灝撅紝浠庤屾垚涓烘湁搴忓簭鍒楃殑涓閮ㄥ垎錛涗笅涓嬈＄戶緇榪欎釜榪囩▼錛岀洿鍒版墍鏈夋暟鎹鍏冪礌閮芥帓濂藉簭銆傜畻娉曠殑鏍稿績鍦ㄤ簬姣忔￠氳繃涓や袱姣旇緝浜ゆ崲浣嶇疆錛岄夊嚭鍓╀綑鏃犲簭搴忓垪閲屾渶澶э紙灝忥級鐨勬暟鎹鍏冪礌鏀懼埌闃熷熬銆

⑷ 八大經典排序演算法原理及實現

該系列文章主要是記錄下自己暑假這段時間的學習筆記，暑期也在實習，抽空學了很多，每個方面的知識我都會另起一篇博客去記錄，每篇頭部主要是另起博客的鏈接。

冒泡排序演算法應該是大家第一個接觸的演算法，其原理都應該懂，但我還是想以自己的語言來敘述下其步奏：

按照計算時間復雜度的規則，去掉常數、去掉最高項系數，其復雜度為O(N^2)
冒泡排序及其復雜度分析

空間復雜度就是在交換元素時那個臨時變數所佔的內存

給定一個整數序列{6,1,2,3,4},每完成一次外層循環的結果為：

我們發現第一次外層循環之後就排序成功了，但是還是會繼續循環下去，造成了不必要的時間復雜度，怎麼優化？

冒泡排序都是相鄰元素的比較，當相鄰元素相等時並不會交換，因此冒泡排序演算法是穩定性演算法

插入排序是對冒泡排序的一種改進

插入排序的思想是數組是部分有序的，再將無序的部分插入有序的部分中去,如圖：
（圖片來自 這里 ）

空間復雜度就是在交換元素時那個臨時變數所佔的內存

插入排序的優化，有兩種方案：

文章後面會給出這兩種排序演算法

由於插入排序也是相鄰元素的比較，遇到相等的相鄰元素時不會發生交換，也不會造成相等元素之間的相對位置發生變化

其原理是從未排序的元素中選出最小值(最大值)放在已排序元素的後面

空間復雜度就是在交換元素時那個臨時變數所佔的內存

選擇排序是不穩定的，比如 3 6 3 2 4，第一次外層循環中就會交換第一個元素3和第四個元素2，那麼就會導致原序列的兩個3的相對位置發生變化

希爾排序算是改良版的插入排序演算法，所以也稱為希爾插入排序演算法

其原理是將序列分割成若乾子序列（由相隔某個 增量 的元素組成的），分別進行直接插入排序；接著依次縮小增量繼續進行排序，待整個序列基本有序時，再對全體元素進行插入排序，我們知道當序列基本有序時使用直接插入排序的效率很高。
上述描述只是其原理，真正的實現可以按下述步奏來：

希爾排序的效率取決於 增量值gap 的選取，這涉及到數學上尚未解決的難題，但是某些序列中復雜度可以為O(N 1.3)，當然最好肯定是O(N)，最壞是O(N 2)

空間復雜度就是在交換元素時那個臨時變數所佔的內存

希爾排序並不只是相鄰元素的比較，有許多跳躍式的比較，難免會出現相同元素之間的相對位置發生變化，所以希爾排序是不穩定的

理解堆排序，就必須得先知道什麼是堆？

二叉樹的特點：

當父節點的值總是大於子結點時為 最大堆 ；反之為 最小堆 ，下圖就為一個二叉堆

一般用數組來表示堆，下標為 i 的結點的父結點下標為(i-1)/2；其左右子結點分別為 (2 i + 1)、(2 i + 2)

怎麼將給定的數組序列按照堆的性質，調整為堆？

這里以建立最小堆為示例，

很明顯對於其葉子結點來說，已經是一個合法的子堆，所以做堆調整時，子節點沒有必要進行，這里只需從結點為A[4] = 50的結點開始做堆調整，即從（n/2 - 1）位置處向上開始做堆調整：

由於每次重新恢復堆的時間復雜度為O(logN)，共N - 1次重新恢復堆操作，再加上前面建立堆時N / 2次向下調整，每次調整時間復雜度也為O(logN)，二次操作時間相加還是O(N logN)。故堆排序的時間復雜度為O(N * logN)。

空間復雜度就是在交換元素時那個臨時變數所佔的內存

由於堆排序也是跨越式的交換數據，會導致相同元素之間的相對位置發生變化，則演算法不穩定。比如 5 5 5 ,堆化數組後將堆頂元素5與堆尾元素5交換，使得第一個5和第三個5的相對位置發生變化

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

快速排序在應該是大家經常看到、聽到的演算法，但是真正默寫出來是有難度的。希望大家看了下面 挖坑填數 方法後，能快速寫出、快速排序。

其原理就這么幾句話，但是現實起來並不是這么簡單，我們採取流行的一種方式 挖坑填數分治法

對於序列： 72 6 57 88 60 42 83 73 48 85

數組變為： 48 6 57 88 60 42 83 73 88 85
再重復上面的步驟，先從後向前找，再從前向後找：

數組變為： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的數字都小於它，a[5]後面的數字都大於它。因此再對a[0…4]和a[6…9]這二個子區間重復上述步驟就可以了

空間復雜度，主要是遞歸造成的棧空間的使用:

快速排序的優化主要在於基準數的選取

快速排序也是跨越式比較及交換數據，易導致相同元素之間的相對位置發生變化，所以快速排序不穩定

前面也說了二分查找排序是改進的插入排序，不同之處在於，在有序區間查找新元素插入位置時，為了減少比較次數提高效率，採用二分查找演算法進行插入位置的確定
具體步驟，設數組為a[0…n]：

二分查找插入位置，因為不是查找相等值，而是基於比較查插入合適的位置，所以必須查到最後一個元素才知道插入位置。
二分查找最壞時間復雜度：當2^X>=n時，查詢結束，所以查詢的次數就為x，而x等於log2n（以2為底，n的對數）。即O(log2n)
所以，二分查找排序比較次數為：x=log2n
二分查找插入排序耗時的操作有：比較 + 後移賦值。時間復雜度如下：

二分查找排序在交換數據時時進行移動，當遇到有相等值插入時也只會插入其後面，不會影響其相等元素之間的相對位置，所以是穩定的

白話經典演算法排序
冒泡排序選擇排序
快速排序復雜度分析
優化的插入排序

⑸ Python冒泡排序注意要點實例詳解

Python冒泡排序注意要點實例詳解
文給大家介紹了python冒泡排序知識，涉及到冒泡排序主要的細節問題，本文通過實例代碼給大家講解，介紹的非常詳細，具有參考借鑒價值，感興趣的朋友一起看看吧
冒泡排序注意三點：
1. 第一層循環可不用循環所有元素。
2.兩層循環變數與第一層的循環變數相關聯。
3.第二層循環，最終必須循環集合內所有元素。
示例代碼一：
1.第一層循環，只循環n-1個元素。
2.當第一層循環變數為n-1時，第二層循環所有元素。
s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
# bubble_sort
for i in range(0, len(s) - 1):
for j in range(i + 1, 0, -1):
if s[j] < s[j - 1]:
s[j], s[j - 1] = s[j - 1], s[j]
for m in range(0, len(s)):
print(s[m])
示例代碼二：
1.第一層循環所有元素。
2.第二層也循環所有元素。
s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
for i in range(0, len(s)):
for j in range(i, 0, -1):
if s[j] < s[j - 1]:
s[j], s[j - 1] = s[j - 1], s[j]
for m in range(0, len(s)):
print(s[m])
以上所述是小編給大家介紹的python冒泡排序演算法注意要點，希望對大家有所幫助