第十三课 一组数组排序及综合应用 目 标 01、学会一维数组的元素排序。 02、 运用一维数组解决实际问题 一维数组的元素排序 “排序”就是按照某个关键字的大小，将若干对象从小到大或者从大到小进行重新排列。关键字是对象的某一个属性，它可以是任何基本数据类型，甚至结构体等。 例如，体育课上我们会按照身高从矮到高站队，这就是“升序”排序，身高是我们每个人的一个属性，也就是排序的关键字。再如，将所有单词按照“字典序”倒过来排序，如zoo,yes,most,key,computer,book,bad,apple等，就是“降序”排序，关键字的类型就是字符串。 排序算法非常多，其中最基本的有选择排序、冒泡排序和插入排序三种。其本质上都是通过数组中的元素比较和交换来实现的，关键是数组下标的分析。 例1、站队 【问题描述】 给出 n 个同学的身高，请根据他们的身高升序排列并输出排序结果。 【输入格式】 第一行 1 个正整数 n，表示有 n 个同学的身高，2 using namespace std; int main(){ int n,i,j,k,temp,h[101]; cin >> n; for(i = 1; i <= n; i++) cin >> h[i]; for(i = 1; i <= n; i++){ k = i; for(j = i+1; j <= n; j++) if(h[j] < h[k]) k = j;// 在 i~n 之间的最小元素 temp = h[i]; h[i] = h[k]; h[k] = temp;// 将 i~n 之间的最小元素放到第 i 个位置 } for(i = 1; i < n; i++) cout << h[i] << “ “ ; cout << h[n] << endl; return 0; } 算法2、冒泡排序 冒泡排序的基本思想是：从第一个数开始，依次不断比较相邻的两个元素，如果“逆序”就交换。这样，一趟排序结束后，最大的元素就放在了第 n 个位置了。对于样例数据，第一趟冒泡排序的过程如下： 用同样的方法，第二趟把剩余的前 n-1 个数中最大的交换到第 n-1 个位置，第三趟把剩余的前 n-2 个数中最大的交换到第 n-2 个位置，……经过 n-1 趟，排序结束。 冒泡排序 #include using namespace std; int main(){ int n,i,j,temp,h[101]; cin >> n; for(i = 1; i <= n; i++) cin >> h[i]; for(i = 1; i < n; i++) for(j = 1; j <= n-i; j++) if(h[j] > h[j+1]){ temp = h[j]; h[j] = h[j+1]; h[j+1] = temp; } for(i = 1; i < n; i++) cout << h[i] << “ “ ; cout << h[n] << endl; return 0; } 对于冒泡排序，我们还可以做些算法“优化”。如果一趟排序下来，都没有任何“逆序”数对，即没有发生“交换”操作，则说明已经排好序了。此时，就可以立刻退出循环。 优化后的冒泡排序 #include using namespace std; int main(){ int n,i,j,temp,h[101]; cin >> n; for(i = 1; i <= n; i++) cin >> h[i]; for(i = 1; i < n; i++){ bool flag = true; for(j = 1; j <= n-i; j++) if(h[j] > h[j+1]){ temp = h[j]; h[j] = ... ...
~~ 您好，已阅读到文档的结尾了 ~~
