今日去參加了幾次面試，發(fā)現(xiàn)有次讓手寫冒泡排序，雖然思路是有的，還是需要鞏固一下，畢竟平時(shí)用的比較少。
比如我們聲明一個(gè)數(shù)組：arr=[9 ,6, 7 ,4, 8, 2]
一、排序?yàn)檫f增數(shù)組序列：
則第0輪排序：我們把第一數(shù)字跟其他的數(shù)字進(jìn)行比對，分別進(jìn)行交換。
1、6 9 7 4 8 2
2、6 7 9 4 8 2
3、6 7 4 9 8 2
4、6 7 4 8 9 2
5、6 7 4 8 2 9
至此，我們找到了最大的數(shù)據(jù)，放到了數(shù)組的末尾
第1輪排序：
1、6 4 7 8 2 9
2、6 4 7 2 8 9
至此，我們找到了第二大的數(shù)據(jù)，放到了數(shù)組的末尾-1
第2輪排序：
1、4 6 7 2 8 9
2、4 6 2 7 8 9
第3輪排序：
1、4 2 6 7 8 9
第4輪排序
1、2 4 6 7 8 9
所以我們可以總結(jié)出以下的規(guī)律：
- N個(gè)數(shù)的數(shù)組，我們外層需要循環(huán)N-1次: 因?yàn)橹灰业搅饲癗-1的大數(shù)，那最小的數(shù)，必然放在最前面了。
- 內(nèi)層循環(huán)每次都會(huì)減少1，因?yàn)槊枯喤藕玫淖畲髷?shù)，需要進(jìn)行排除，同時(shí)還要排除掉自身。
說明：比如第1輪的排序，我們需要排除掉自身（-1），排除掉已經(jīng)排好的最大數(shù)9（最大數(shù)個(gè)數(shù)1個(gè) = i個(gè)）
代碼實(shí)現(xiàn)：
a = [9, 6, 7, 4, 8, 2]
n = len(a)
for i in range(0, n-1):
print("第" + str(i) + "輪排序")
for j in (range(0, n-i-1)):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
print(a)
image.png
二、看排序算法的時(shí)間復(fù)雜度O(n)
我們常說的時(shí)間復(fù)雜度，其實(shí)是最壞時(shí)間復(fù)雜度，計(jì)算方式采用大O階公式進(jìn)行計(jì)算：時(shí)間復(fù)雜度計(jì)算，在此不再進(jìn)行贅述。
那最壞的情況是數(shù)組：[9,8,7,6,4,2]
所以我們可以看到此具體實(shí)例中的比較次數(shù)：
第一次比較5次：
第二次比較4次；
第三次比較3次；
第四次比較2次；
第五次比較1次；
即 5 + 4 + 3 + 2 + 1 = 15次
此時(shí)我們將數(shù)組的個(gè)數(shù)設(shè)置為N，則時(shí)間復(fù)雜度計(jì)算為：
N-1 + N-2 + N -3 + .... + 1 = N(N-1) /2
根據(jù)大O階公式計(jì)算出，冒泡排序的時(shí)間復(fù)雜度為 O(n^2)
