大學(xué)計算機基礎(chǔ)-基于計算思維（Windows 10+Office 2016）（第2版）課件 10.3.1冒泡排序

大學(xué)計算機基礎(chǔ)——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.3.1冒泡排序10.3排序算法基本排序算法冒泡排序冒泡排序選擇排序直接插入排序問題3冒泡排序大學(xué)入學(xué)軍訓(xùn)時要求n人一列從低到高排列，現(xiàn)在已知n人的身高（無序），請按要求完成任務(wù)。1.問題分析冒泡排序的過程類似水中冒氣泡的過程，將待排序的n個身高數(shù)據(jù)看作是垂直排列的重量不同的氣泡。根據(jù)重氣泡不能在輕氣泡上面的原則，從上往下掃描，比較相鄰數(shù)據(jù)，如果它們是逆序的話就交換它們的位置，重復(fù)多次后，最大數(shù)據(jù)就“沉到”了最后位置，稱為第1趟掃描冒泡。問題3冒泡排序1.問題分析第2遍操作對剩余的數(shù)據(jù)進行掃描冒泡，將第二大的數(shù)據(jù)沉下去。這樣一直做，經(jīng)過n-1趟以后，所有數(shù)據(jù)就排好序了。問題3冒泡排序2．算法實現(xiàn)（1）設(shè)計輸入子程序input。先設(shè)計一個子程序來完成數(shù)據(jù)的輸入功能（名稱為input），要求生成n個150~190的隨機整數(shù)存儲到數(shù)組a[]中。數(shù)組名a作為“輸出”參數(shù)，如圖所示為input的各接口參數(shù)問題3冒泡排序2．算法實現(xiàn)（1）設(shè)計輸入子程序input。在子程序中要生成n個150~190的隨機整數(shù)存儲到a[]數(shù)組中，可設(shè)計一個循環(huán)結(jié)構(gòu)（設(shè)循環(huán)變量為i，從1遞增到n）由隨機函數(shù)構(gòu)建公式產(chǎn)生1個150~190的隨機整數(shù)存放到數(shù)組a[i]元素中問題3冒泡排序2．算法實現(xiàn)（2）設(shè)計輸出子程序output。設(shè)計一個子程序來完成數(shù)據(jù)的輸出功能（名稱為output），要求將上述數(shù)組a[]中的所有數(shù)據(jù)輸出，數(shù)據(jù)間用空格分隔。在創(chuàng)建子程序output時，要已知數(shù)組的大小n和數(shù)組名a，而且在output中都不會改變其值，所以n和a都作為“輸入?yún)?shù)”問題3冒泡排序2．算法實現(xiàn)（2）設(shè)計輸出子程序output。在子程序output中要輸出a數(shù)組中所有元素，可設(shè)計一個循環(huán)結(jié)構(gòu)（設(shè)循環(huán)變量為i，從1遞增到n），在循環(huán)體內(nèi)按格式輸出數(shù)組元素a[i]。問題3冒泡排序2．算法實現(xiàn)（3）設(shè)計main子圖main子圖的主要功能是：①輸入要排隊列人數(shù)n。②調(diào)用input子程序生成數(shù)組a，模擬待排人的身高數(shù)據(jù)。③調(diào)用output子程序顯示數(shù)組a（無序）。問題3冒泡排序2．算法實現(xiàn)（3）設(shè)計main子圖右圖所示為該程序調(diào)試運行中的一組數(shù)據(jù)（10個）問題3冒泡排序（4）設(shè)計冒泡子程序bubble表中列出了a數(shù)組有5個元素的冒泡排序過程。問題3冒泡排序（4）設(shè)計冒泡子程序bubble從表中，我們要找出a數(shù)組有n個元素時冒泡排序的一般規(guī)律。問題3冒泡排序（4）設(shè)計冒泡子程序bubble完成bubble子程序，實現(xiàn)步驟如下：①創(chuàng)建bubble子程序，其各參數(shù)如圖所示。問題3冒泡排序（4）設(shè)計冒泡子程序bubble②在bubble子程序中首先構(gòu)建掃描冒泡趟數(shù)的循環(huán)i（1～n-1）。③然后在每趟冒泡i的循環(huán)體內(nèi)再構(gòu)建一個比較次數(shù)的循環(huán)j（從上往下掃描1～n-i）。④在內(nèi)循環(huán)j的循環(huán)體內(nèi)，從上到下比較相鄰元素，若a[j]>a[j+1]則交換其中的內(nèi)容。問題3冒泡排序（5）完善main子圖①調(diào)用bubble子程序，對數(shù)組a進行冒泡排序。②調(diào)用output子程序