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

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