基本概念
（一）常見排序算法可以分為兩大類：
1、比較類排序：通過比較來決定元素間的相對次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)，因此也稱為非線性時(shí)間比較類排序。
2、非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時(shí)間下界，以線性時(shí)間運(yùn)行，因此也稱為線性時(shí)間非比較類排序。
3、常見的排序算法
二、交換排序-冒泡排序基本概念
（一）概念：冒泡排序是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
（二）原理：比較兩個(gè)相鄰的元素，將值大的元素交換到右邊
（三）動(dòng)圖：
（四）思路：
1、第一趟比較：
（1）第一趟中第一次比較：首先比較第一和第二個(gè)數(shù)，將小數(shù)放在前面，將大數(shù)放在后。
（2）第一趟中第二次比較：第2和第3個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。
（3）第一趟中第三次比較：第3和第4個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。
（4）以此類推，直到比較到最后的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面
2、第二趟比較：
在第一趟比較完成后，最后一個(gè)數(shù)一定是所有數(shù)中最大的一個(gè)數(shù)，所以在比較第二趟的時(shí)候，最后一個(gè)數(shù)是不參加比較的。
（1）第二趟中第一次比較：首先比較第一和第二個(gè)數(shù)，將小數(shù)放在前面，將大數(shù)放在后。
（2）第二趟中第二次比較：第2和第3個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。
（3）第二趟中第三次比較：第3和第4個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。
（4）以此類推，直到比較到倒數(shù)第一和倒數(shù)第二的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。
3、第三趟比較：
在第二趟比較完成后，倒數(shù)第二個(gè)數(shù)也一定是數(shù)組中倒數(shù)第二大數(shù)，所以在第三趟的比較中，最后兩個(gè)數(shù)是不參與比較的。
比較方式和上面兩趟示例一樣，不作一一敘述。
三、常規(guī)實(shí)現(xiàn)
1、首先先準(zhǔn)備一串?dāng)?shù)字，循環(huán)得到比較的趟數(shù)，如下：
代碼：
def bubble_sort(nums):
? ? num = len(nums)
? ? print('共有%d個(gè)數(shù)'%num)
? ? for i in range(len(nums) - 1):
? ? ? ? # range(len(nums) - 1) 最后一趟已經(jīng)比較完成，不需要再比較 所以總數(shù)減去1個(gè)
? ? ? ? print('第%d趟'%i)
if __name__ == '__main__':
? ? listData = [1, 2, 3, 10, 5, 9, 7, 8, 6, 4]
bubble_sort(listData)
2、利用雙重循環(huán)，得到每一趟中比較的次數(shù)，如下：
代碼：
def bubble_sort(nums):
? ? num = len(nums)
? ? print('共有%d個(gè)數(shù)'%num)
? ? for i in range(len(nums) - 1):
? ? ? ? # range(len(nums) - 1) 最后一趟已經(jīng)比較完成，不需要再比較 所以總數(shù)減去1個(gè)
? ? ? ? print('第%d趟'%i)
? ? ? ? for j in range(len(nums) - i - 1):
? ? ? ? ? ? print('第%d次' % j)
if __name__ == '__main__':
? ? listData = [1, 2, 3, 10, 5, 9, 7, 8, 6, 4]
? ? bubble_sort(listData)
3、每一次都將當(dāng)前的數(shù)和后一次的數(shù)進(jìn)行比較，將大的數(shù)放到后面，如下：
代碼：
def bubble_sort(nums):
? ? print('比較前的數(shù)據(jù):',nums)
? ? num = len(nums)
? ? for i in range(len(nums) - 1):
? ? ? ? for j in range(len(nums) - i - 1):
? ? ? ? ? ? if nums[j] > nums[j + 1]:
? ? ? ? ? ? ? ? nums[j], nums[j + 1] = nums[j + 1], nums[j]
? ? print('比較后的數(shù)據(jù):',nums)
if __name__ == '__main__':
? ? listData = [1, 2, 3, 10, 5, 9, 7, 8, 6, 4]
? ? bubble_sort(listData)
4、修改打印顯示下每一次的比較結(jié)果，如下：
四、算法分析
1、如果有5個(gè)數(shù)要排序，總共進(jìn)行4趟排序：
（1）第一趟中比較排序的次數(shù)是3次。
（2）第二趟中比較排序的次數(shù)是2次。
（3）第三趟中比較排序的次數(shù)是1次。
運(yùn)行程序：
2、還成多個(gè)數(shù)按照這個(gè)規(guī)律總結(jié)一下：N個(gè)數(shù)字要排序完成，總共進(jìn)行N-1趟排序，每i趟的排序次數(shù)為(N-i)次。所以使用雙重循環(huán)語句，外層控制循環(huán)多少趟，內(nèi)層控制每一趟的比較次數(shù)。
3、優(yōu)點(diǎn)：每進(jìn)行一趟排序，就會(huì)少比較一次，因?yàn)槊窟M(jìn)行一趟排序都會(huì)找出一個(gè)較大值。如上例：第一趟比較之后，排在最后的一個(gè)數(shù)一定是最大的一個(gè)數(shù)，第二趟排序的時(shí)候，只需要比較除了最后一個(gè)數(shù)以外的其他的數(shù)，同樣也能找出一個(gè)最大的數(shù)排在參與第二趟比較的數(shù)后面，第三趟比較的時(shí)候，只需要比較除了最后兩個(gè)數(shù)以外的其他的數(shù)，以此類推，也就是說，每進(jìn)行一趟比較，就少比較一次，一定程度上減少了運(yùn)行次數(shù)。
4、時(shí)間復(fù)雜度
（1）如果我數(shù)據(jù)是正序，有n個(gè)數(shù)，只需要走一趟即可完成排序。所需的比較次數(shù)C和記錄移動(dòng)次數(shù)M均達(dá)到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的時(shí)間復(fù)雜度為O(n)。
（2）如果很不幸我們的數(shù)據(jù)是反序的，則需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次比較(1≤i≤n-1)，且每次比較都必須移動(dòng)記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動(dòng)次數(shù)均達(dá)到最大值。
（3）冒泡排序總的平均時(shí)間復(fù)雜度為：O(n2) ,時(shí)間復(fù)雜度和數(shù)據(jù)狀況無關(guān)
（4）借用一個(gè)圖表示
其中穩(wěn)定性的意思是：在比較的過程中，兩個(gè)數(shù)在整個(gè)過程的位置前后關(guān)系不會(huì)發(fā)生任何變化，那么算法就是穩(wěn)定的。
5、空間復(fù)雜度
算法的內(nèi)存消耗可以通過空間復(fù)雜度來衡量，冒泡排序僅需要一個(gè)變量tmp來儲(chǔ)存交換的數(shù)據(jù)，因此空間復(fù)雜度為 O(1)，另外空間復(fù)雜度為 O(1) 的排序算法，也叫原地排序算法
五、代碼改進(jìn)
1、上面的冒泡排序算法在遇到有序的數(shù)列時(shí)，算法復(fù)雜度是O(n)，也就是說1,2,3,4,5,6這樣的一個(gè)有序數(shù)組，它仍然需要循環(huán)比較一次，這就浪費(fèi)了時(shí)間和空間，所以需要做一些改進(jìn)。
2、改進(jìn)代碼如下，其中bubble_sort_ex通過設(shè)置標(biāo)志位先判斷是否數(shù)列有序。
def bubble_sort(nums):
? ? print('比較前的數(shù)據(jù):',nums)
? ? num = len(nums)
? ? for i in range(len(nums) - 1):
? ? ? ? for j in range(len(nums) - i - 1):
? ? ? ? ? ? if nums[j] > nums[j + 1]:
? ? ? ? ? ? ? ? nums[j], nums[j + 1] = nums[j + 1], nums[j]
? ? ? ? ? ? print('第%d趟第%d次比較'%(i, j))
? ? ? ? ? ? print(nums)
? ? print('比較后的數(shù)據(jù):',nums)
def bubble_sort_ex(nums):
? ? for i in range(len(nums) - 1):
? ? ? ? ex_flag = False? # 設(shè)置一個(gè)交換標(biāo)志位
? ? ? ? for j in range(len(nums) - i - 1):
? ? ? ? ? ? if nums[j] > nums[j + 1]:
? ? ? ? ? ? ? ? nums[j], nums[j + 1] = nums[j + 1], nums[j]
? ? ? ? ? ? ? ? ex_flag = True
? ? ? ? if not ex_flag:
? ? ? ? ? ? return nums? # 已經(jīng)有序了可以返回?cái)?shù)據(jù)了
? ? return nums
if __name__ == '__main__':
? ? listData = [1, 10, 5, 9]
? ? bubble_sort_ex(listData)
