计算基础教程 1

授课内容排序学时4教学目标知识目标理解排序的核心概念及分类标准掌握冒泡、选择、快速排序的原理与步骤了解插入、归并等排序算法的核心特点掌握STL中sort函数的基本用法能力目标提升各类排序算法的逻辑分析与流程设计能力培养根据数据场景择优选取排序算法的实践能力强化排序算法的应用与问题解决能力重点与难点重点冒泡排序的原理、程序实现及提前退出技巧选择排序的核心思路与程序实现方法快速排序的分治思想与基准值划分流程STL中sort函数的使用及自定义排序规则难点快速排序中基准值的选择与递归分治逻辑的理解根据数据特征与需求，合理选择适配的排序算法教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接递归算法，学习实用的排序算法知识排序在生活和编程中应用广泛，是算法学习的核心内容掌握排序算法是应对竞赛、考级的重要基础不同排序算法各有优劣，学会择优使用是核心能力通过本章学习，夯实算法设计与问题解决的实操基础第二部分：新课讲解一、排序问题概述1、排序的算法排序的算法竟然多达十几种！这些算法各有优缺点，没有一种是非常完美的。它们各自适用于不同的情况，因而都有存在的必要。2、相关概念比较排序和非比较排序比较排序是通过比较大小来决定数据间的相对次序；非比较排序则不是通过比较大小来决定数据间的相对次序。非比较排序包括计数排序、桶排序和基数排序，其余常见的排序算法都是比较排序。排序的稳定性排序分为稳定排序和不稳定排序二大类。稳定排序，就是如果a在b前面，而且a=b，排序之后a仍然在b的前面。不稳定排序：如果a在b的前面，而且a=b，排序之后a可能会出现在b的后面。二、冒泡排序1、概述冒泡排序（BubbleSort）是一种最基础的交换排序，其特点是比较和交换。冒泡排序模拟了水中的气泡溢出过程过程，通过不停地相邻交换，使得大的数据不停地向后移动，最终达到正确的位置。2、第一趟冒泡第一趟冒泡的目的，是将数列中的最大值通过交换移动到数列的最后面去。具体步骤为：（1）先检查前二个数，发现第一个数5小于后面的6，即它们是有序的，所以不需要进行任何处理，如下图(a)所示。（2）检查第2，3个数，发现前面的6大于后面的3，这时需要将它们交换位置，如下图(b)所示。后续数据的比较处理依次类推，最终，经过这一趟冒泡，最大值6交换到了数列的尾部。3、后续的冒泡过程后续冒泡过程与第一趟类似，每次都实现将前面未排序数据中的最大值移动此区域的尾部。4、特点总结n个数据的排序，需要进行n-1轮冒泡。对于第i轮冒泡，其比较次数为n-1-i次。5、核心程序constintn=10; //定义常量n，它代表10 inta[n]={8,2,5,34,6,12,65,22,16,55}; for(inti=0;i<n-1;i++) //外层循环n-1次{ for(intj=0;j<n-1-i;j++) //内层循环n-1-i次 { if(a[j]>a[j+1]) //需要将a[j]与a[j+1]交换 { inttemp; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } }6、例题：车厢重组题目在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。【输入数据】输入数据有两行，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。【输出数据】一个数据，是最少的旋转次数。解析车厢重组的过程完全就是冒泡排序的过程，只是需要增加统计交换次数功能。程序详见课本说明这个例子同时展示了冒泡排序的提前退出功能。三、选择排序1、基本思想先从未排序的数据中选出最小的，然后直接与第1个数据交换位置。这样，就将最小元素移到了其正确的位置上去。再针对剩余数据，重复以上步骤，直到全部数据都有序为止。2、排序过程初始数据（数组a）： 563412第一趟：在a[0]～a[5]中选择最小者，然后与a[0]处的元素交换，结果：163452第二趟：在a[1]～a[5]中选择最小者，然后与a[1]处的元素交换，结果：123456第三趟：在a[2]～a[5]中选择最小者，然后与a[2]处的元素交换，结果：123456其余各趟依次类推。3、程序详见课本要点：针对最小元素，记录其下标，而不是最小元素的值。四、快速排序1、算法思想先从待排序数据中任取一个数据作为基准值，然后将大于基准值的数据全部移到基准值的后面，而将小于基准值的数据全部移到基准值的前面。这一操作完成之后，基准值就在正确的位置处。并且以基准值为分割线，在其左右形成了二个较小的未排序数据区。然后再对这二个子集进行同样的操作（递归处理），就可以完成全部数据的排序。在递归过程中，会层层减小子集的规模，当子集减小到只有一个元素时，就可以停止递归了。2、准备工作排序开始前，需要准备3个变量。一个用于存储基准值，另外二个是首尾指针，分别指向待排序数据区的首元素与末元素，如下图所示：3、第一轮处理先从尾指针开始，向前寻找第一个小于基准值的数据。然后，再从头指针开始，向后寻找第一个大于基准值的数据。整个过程如下图所示。然后，交换上述二个指针处的数据。操作完成之后，前后指针并未“碰头”（即未完成对全部数据的扫描），因此，还需要再继续处理。重复上述操作后，头指针与尾指针最终将“碰头”，如下图所示。将头/尾指针处的数据与作为基准值的那个数据交换，第一轮搜索与交换完成。4、后续处理这一轮搜索与交换结束后，基准值3到达了正确的位置处，但基准值前后的数据区仍为未排序区。只需要再针对这二段未排序区域重复进行上述操作（通过递归调用实现），就可以完成全部数据的排序。5、程序voidquick_sort(inta[],intleft,intright){ if(left>=right)return; intL=left,R=right; intkey=a[L]; while(L<R) { while(L<R&&a[R]>=key)R--; //从右向左找比key小的值 while(L<R&&a[L]<=key)L++; //从左向右找比key大的值 if(L<R) swap(a[L],a[R]); //交换二个值，if条件可不要 } swap(a[left],a[L]); //将基准key交换到正确位置处 qsort(a,left,L-1); //递归，再完成左半区间的排序 qsort(a,R+1,right); //递归，再完成右半区间的排序}6、例题：第k小整数题目给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数。【输入格式】第一行包含两个整数n和k。（1≤n≤100000，1≤k≤n）第二行包含n个整数（所有整数均在1∼109范围内），表示整数数列。【输出格式】输出一个整数，表示数列的第k个数。解析这个题目，就是在快速排序过程中，不断检查一下第k个数应该位于基准值的哪一侧，从而只对第k个数所在的那一个子集进行排序，而另一个子集则不需要排序，从而节约时间。程序详见课本五、其它排序算法1、插入排序原理回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边将牌按花色和大小插入到恰当的位置处。当抓完所有的牌时，手中的牌便是有序的，这排序方法就是插入排序。当读入一个元素时，在已经排序好的序列中，搜寻它的正确位置。找到之后，将插入点之后的元素后移一位，腾出一个空位，再将新元素放入即可。当全部数据读取完毕后，数组就是有序的。图示及程序详见课本2、归并排序原理“归并”的含义就是“合并”，它是通过将两个或两个以上的有序表不断合并成一个新的有序表的方式来实现排序的。图示分析详见课本3、基数排序与计数排序了解，详见课本六、STL中的排序函数1、概述STL中文名称为标准模板库，它是容器、算法和其它一些组件的集合。STL中的排序函数中，sort函数的使用频率最高。2、sort函数基本用法sort(start,end