常見的排序算法-冒泡排序 課件 2023-2024學年浙教版（2019）高中信息技術選修1

第五章數(shù)據(jù)結構與算法選修一《數(shù)據(jù)與數(shù)據(jù)結構》5.3.2常見的排序算法——冒泡排序排序就是整理數(shù)據(jù)的序列，使其中元素按照某個值遞增（或遞減）的次序重新排列的操作。排序是什么？太抽象了，無法理解排序是什么？1891412718914127按數(shù)組形式進行存儲18914127按鏈表形式進行存儲79121418對數(shù)組進行升序排序Python中的排序實現(xiàn)第一種：列表自帶的sort算法列表自帶的sort方法，只適用于列表，直接對列表進行排序，不會產(chǎn)生新的序列。第二種：內(nèi)建函數(shù)sorted方法內(nèi)建函數(shù)sorted方法，返回一個新的序列，原來序列依然存在。a=[5,7,6,3,4,1,2]a.sort()print(a) #[1,2,3,4,5,6,7]a=[5,7,6,3,4,1,2]a.sort(reverse=True)print(a) #[7,6,5,4,3,2,1]a=[5,7,6,3,4,1,2]b=sorted(a)print(a) #[5,7,6,3,4,1,2]print(b) #[1,2,3,4,5,6,7]常見的排序算法—冒泡排序冒泡排序是在一系列數(shù)據(jù)中對相鄰兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)“下沉（上冒）”，較小的數(shù)“上冒（下沉）”的一種排序技術。18914127p[0]p[1]p[2]p[3]p[4]91814127914181279141218791412718冒泡排序算法對數(shù)組p做的第1遍加工常見的排序算法—冒泡排序91412718914127189121471891271418冒泡排序算法對數(shù)組p做的第2遍加工冒泡排序算法對數(shù)組p做的第3遍加工912714189127141897121418常見的排序算法—冒泡排序9712141879121418冒泡排序算法對數(shù)組p做的第4遍加工對長度為5的數(shù)組p，一共需要4次加工對長度為n的數(shù)組p①一共需要(n-1)次加工②在第i遍加工當中，共需比較(n-i)次

①一共需要(n-1)次加工常見的排序算法—冒泡排序91412718912714189712141879121418排好第1大的元素排好第2大的元素排好第4大的元素排好第3大的元素每一次加工，都是為了排好未排序數(shù)據(jù)當中最大的元素常見的排序算法—冒泡排序②在第i遍加工當中，共需比較(n-i)次n=5i=1n-i=4排好元素：i-1=0個共有n-(i-1)=5個元素需要比較兩兩比較需要比較4次常見的排序算法—冒泡排序②在第i遍加工當中，共需比較(n-i)次n=5i=2n-i=3排好元素：i-1=1個共有n-(i-1)=4個元素需要比較兩兩比較需要比較3次常見的排序算法—冒泡排序②在第i遍加工當中，共需比較(n-i)次n=5i=3n-i=2排好元素：i-1=2個共有n-(i-1)=3個元素需要比較兩兩比較需要比較2次n=5i=4n-i=1排好元素：i-1=3個共有n-(i-1)=2個元素需要比較兩兩比較需要比較1次如果說一共有n個元素，第i遍加工當中共有(n-i+1)個元素需要比較兩兩比較需要比較(n-i)次常見的排序算法—冒泡排序

第1遍加工：比較（n-1）次第2遍加工：比較（n-2）次…第（n-2）遍加工：比較2次第（n-1）遍加工：比較1次①一共需要(n-1)次加工Q：一共需要幾次加工？

總共需要比較次數(shù)S冒泡排序算法實現(xiàn)自主閱讀課本第130頁，思考一共需要幾個變量？每個變量的作用是什么？i：記錄當前正進行的處理遍數(shù)j：記錄當前數(shù)組元素的下標。每遍處理過程中，j總是從第一個數(shù)據(jù)元素，下標為0開始。按每次加1的方式直至j+1=n-i=>j=n-i-1為止每次比較p[j]與p[j+1]進行比較，若p[j]>p[j+1]，則進行互換i=2j=0j+1j=1j+1j=2j+1j=3j+1i=1i=1i=1i=1j=0j+1j=1j+1j=2j+1i=2i=2i=3i=3i=4j=0j+1j=1j+1j=0j+1每遍處理過程中，j總是從第一個數(shù)據(jù)元素，下標為0開始。按每次加1的方式直至j+1=n-i=>j=n-i-1為止每次比較p[j]與p[j+1]進行比較，若p[j]>p[j+1]，則進行互換冒泡排序算法實現(xiàn)i：記錄當前正進行的處理遍數(shù)j：記錄當前數(shù)組元素的下標。①一共需要(n-1)次加工冒泡排序算法實現(xiàn)Python代碼實現(xiàn)defbubble_sort(p):length=len(p)foriinrange(1,length):forjinrange(0,length-i):ifp[j]>p[j+1]:temp=p[j]p[j]=