《程序设计综合实践》-第3章 查找和排序-第5次课

课前视频学习任务3.1查找和简单排序（时长：10分36秒）3.2归并排序和快速排序（时长：16分55秒）3.3其它特殊排序方法（时长：11分50秒）课前实践任务预先实现各排序算法，准备课堂讨论和实现评测。课堂测试（5分钟）课堂提问（30分钟）课堂提问问题1：顺序查找和二分查找的区别。//算法3.1在n个元素的数组A中顺序查找是否存在元素关键字为key，存在返回下标；不存在返回-1intSequentialSearch(ElemTypeA[],intn,KeyTypekey){for(i=0;i<n;++i)if(A[i].key==key)returni;return-1;}课堂提问//算法3.2在n个元素的递增排序数组A中进行二分查找，存在时，返回下标；不存在时返回-1intBinarySearch(ElemTypeA[],intn,KeyTypekey){low=0;high=n-1;while(low<=high){middle=(low+high)/2;//获取中间位置下标if(A[middle].key==key)returnmiddle;//查找到if(A[middle].key>key){high=middle-1;//继续在前半段查找}elselow=middle+1;//继续在后半段查找}return-1;//确定没有}课堂提问问题2：冒泡排序方法思路//算法3.3冒泡排序。对存放n个元素的数组按关键字递增排序voidBubbleSort(ElemTypeA[],intn){for(i=0;i<n-1;++i)//冒泡遍数控制for(j=0;j<n-i-1;++i)//子序列范围{if(A[j].key>A[j+1].key)//元素次序不符swap(A[j],A[j+1])//交换元素}}/zcl_love_wx/article/details/83576962课堂提问问题3：选择排序方法思路//算法3.4简单选择排序。对存放n个元素的数组按关键字递增排序voidSelectSort(ElemTypeA[],intn){for(i=0;i<n-1;++i)//选择遍数控制{minI=i;//初始最小元素位置for(j=i+1;j<n;++i)//选择比较范围{if(A[minI].key>A[j].key)minI=j;//迭代最小元素所在位置}swap(A[i],A[minI]);//交换两个元素}}//算法3.4直接插入排序。对存放n个元素的数组按关键字递增排序voidInsertionSort(ElemTypeA[],intn){for(i=1;i<n;++i)//插入遍数控制{x=A[i];//取出待插入元素，便于前面元素后移j=i-1;//从子序列最后一个元素位置开始while(j>=0&&x.key<A[j].key)//需要后移元素{A[j+1]=A[j];//后移一个位置--j;//从后往前查找插入位置}A[j+1]=x;//完成插入}}8课堂提问问题5：归并排序算法思路//算法3.5归并排序。对存放n个元素的数组按关键字递增排序voidMergeSort(ElemTypeA[],intlow,inthigh,ElemTypeAux[]){if(low>=high)return;//规模不超过1，无需排序m=(low+high)div2;//二分法划分MergeSort(A,low,m，Aux);//前一半子序列排序MergeSort(A,m+1,high，Aux);//后一半子序列排序Merge(A,low,m,high,Aux);//归并两段有序子序列for(i=low;i<=high;++i)A[i]=Aux[i];//移动回原数组}10

//归并排序中有序段合并子算法voidMerge(ElemTypeA[],intlow,intm,inthigh,ElemTypeAux[]){i=low;//前段有序子序列起点j=m+1;//后段有序子序列起点k=i;//归并结果起始下标while(i<=m&&j<=high){//较小元素先转移至结果缓冲区if(A[i].key<=A[j].key)Aux[k++]=A[i++];elseAux[k++]=A[j++];}

11while(i<=m)//前段剩余元素转移至结果缓冲区Aux[k++]=A[i++];while(j<=high)//后段剩余元素转移至结果缓冲区Aux[k++]=A[j++];}12

13课堂提问问题6：快排算法思路//算法3.6a快速排序递归部分。对存放n个元素的数组按关键字递增排序voidQuickSort(ElemTypeA[],intlow,inthigh){if(low>=high)return;//规模不超过1的子序列无需排序pivot=QuickPass(A,low,high);//快速划分，返回划分后枢轴元素所在位置QuickSort(A,low,pivot-1);//对前一段子序列快速排序QuickSort(A,pivot+1,high);//对后一段子序列快速排序}15

16图3.2b快速排序中快速划分示意图//算法3.6b快速排序划分部分。intQuickPass(ElemTypeA[],intlow,inthigh){ElemTypex=A[low];//枢轴元素while(low<high){while(low<high&&x.key<=A[high].key)--high;//从右往左扫描，保留右边大于等于枢轴元素的所有元素位置不变if(low==high)break;A[low++]=A[high];//较小元素从右边移至左边空余位置

17while(low<high&&x.key>=A[low].key)++low;//从左往右扫描，保留左边小于等于枢轴元素的所有元素位置不变if(low==high)break;A[high--]=A[low];//较大元素从左边移至右边空余位置}A[low]=x;//枢轴元素放回空余位置returnlow;//返回枢轴元素所在位置}

18作业解题思路5分钟排序算法实现与性能分析、评测：编写程序，实现上述冒泡排序、简单选择排序、简单插入排序、归并排序、快速排序函数和其它各类排序算法，并产生规模分别为100、1000、10000、100000、1000000的模拟数组，使用上述排序方法分别对同样的模拟数据进行排序，在验证排序结果正确性的同时，利用系统时间函数分别记录各排序开始前时间和排序完成时时间，计算出各排序所需时间。再对已排序数据稍加次序调整，模拟几乎有序数组，再重复上述排序过程。总结、分析上述程序运行结果。解题思路：（1）先实现可对整型元素数组排序的题目里各指定算法的通用函数；（2）使用随机数函数生成具有指定个数元素的数组，评测每个排序算法效率时，先将需排序的数组复制一份为待排序数组，然后调用系统时钟函数获取排序前系统时间，再调用排序函数完成排序，再次调用系统时钟函数获取排序完成时系统时间，前后两个时间相减为该排序算法实际耗费时间；可用随机调整几对已排序数组数据来模拟几乎有序数组排序。（3）排序的正确性可用一个Check检查函数来检验。（4