（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第5讲 排序1

学科竞赛编程 C++ NOIP NOI IOI 1 1 PART ONE 认识排序 1 2 排序又称“分类"。按关键字大小递增或递减的次序,对文件中的全部记录重新排列的过程。 排序是计算机程序设计中的种重要运算。分内部排序和外部排序两大类。内部排序中常用的 方法有选择排序、冒泡排序、插入排序、哈希排序、快速排序、归并排序等。又称分类。 2. 排序在生活中的例子 一学期成绩排序 文件按名称排序 1 PART ONE 基本思想  动画演示  每一趙从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在待排序的数列的最前面,直到全部待排序的数据元素排完。 选择排序 1 PART ONE 【问题描述】将49,38,65,97,76,13,27,49 依据选择排序的思想从小到大排序。 【样例输出】13 27 38 49 49 65 76 97 选择排序的过程 【过程分析】 第二步:选出剩下7个数中最小数字和第2个数字交换位置。 1 PART ONE 第三步: 选出剩下6个数中最小数字和第3个数字交换位置 第四步:选出剩下5个数中最小数字和第4个数字交换位置 第五步:选出剩下4个数中最小数字和第5个数字交换位置 1 PART ONE 第六步: 选出剩下3个数中最小数字和第6个数字交换位置。 第七个:选出剩下2个数中最小数字和第7个数字交换位置,最后一个数字已经 是最大的数字了,这样得到了排列好的数字列 使用选择排序顺序输出. 【可题描述】 输入n个整数,将n个数按从小到大的顺序输出(n<=10000)。 【样例输入】 8 49 38 65 97 76 13 27 49 【样例输出】 13 27 38 49 49 65 76 97 选择排序的应用 1 PART ONE (1) 读入数据存放在a数组中。 (2) 在a[1]~a[n]中选择值最小的元素,与第1位置元素进行交换,则把最小值元素 放入a[1]中 (3) 在a[2]~a[n]中选择值最小的元素,与第2位置元素进行交换,则把最小元素 放入a[2]中 (4) 直到第n-1个元素与第n个元素比较排序为止 【问题分析】 1 PART ONE #include <iostream〉 using namespace std; const int MAXN= 10001; int main(){ int n, k, i,j; int a[MAXN]; cin>>n; for(i=0;i<n;i++) cin > a[i]; for(i=0;i<n;i++){ k=i; for(j=i+1;j<n;j++){ if(a[j]<a[k]) k=j; } if(k!=i) swap(a[i],a[k]); } for(i=0;i<n;i++) cou<< a[i]<<” ”; return 0; } 完整代码 1 PART ONE 基本思想  从无序序列头部开始,相邻元素进行两两比较,根据大小交换位置,直到最后将最大(小)的数据元素交换到了无序队列的队尾,从而成为有序序列的部分;下一次继续这个过程,直到所有数据元素都排好序。 冒泡排序 动画演示  1 PART ONE 2. 冒泡排序的过程 (1)比较相的元素。如果第一个比第二个大(小),就交換他们门两个 (2)对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一 对。这步做完后,最后的元素会是最大(小)的数 (3)针对所有的元素重复以上的步骤,除了最后已经选出的元素(有序)。 (4)持续每次对越来越少的元素(无序元素)重复上面的步骤,直到没有任何一对数字需要比较,则序列最终有序。 3. 冒泡排序的过程图示 【问题描述】使用冒泡排序的方法将数列6,5,3,4,1,2从小到大排序。 【样例输出】123456 第一步 : 把6个数中最大的数字放到第6个方格的位置上。 1 PART ONE 第二步:把剩下5个数中最大的数字放在第5个方格的位置上。 第三步:把剩下4个数中最大的数字放在第4个方格的位置上。 3 4 1 2 5 6 3 1 4 2 5 6 3 1 2 4 5 6 1 PART ONE 1 3 2 4 5 6 第四步:把剩下3个数中最大的数字放在第3个方格的位置上。 1 2 3 4 5 6 第五步: 把剩下2个数中较大的数字放在第2个方格的位置上。 1 2 3 4 5 6 使用冒泡排序顺序输出。 【问题描述】 输入n个整数,将n个