《常用软件算法基础》课件-第9章 学生基本信息排序

第九章学生基本信息排序内容目标：排序的基本概念。学生基本信息直接插入排序案例分析学生基本信息折半插入排序案例分析学生基本信息冒泡排序案例分析学生基本信息选择排序案例分析学生基本信息快速排序案例分析重难点：学生基本信息各类排序的实现1.1功能描述学生基本信息排序表：1.2功能描述学生基本排序界面设计如下：2.1排序的基本概念基本概念排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~排序分类按待排序记录所在位置内部排序：待排序记录全部存放在内存中进行排序的过程。外部排序：指待排序的记录数量，以致内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序2.2排序的基本概念按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(logn)排序基本操作比较两个关键字的大小将记录从一个位置移动到另一个位置。前一种操作对大多数排序方式来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。3.1.1业务实现---直接插入排序3.1.2业务实现---直接插入排序具体实现的步骤如下：我们用一个一维数组来装载排序好的结果。数组下标为0的元素记录每次要进行插入排序的元素，下标为1、2…N记录是已由小到大排好的元素。当向一个数组插入第一个元素时，放置在下标为0和1的位置，这时认为第一个元素已经排好序。在向数组插入第2个元素时，首先放置在下标为0的位置，让它与第1个元素比较，如果比它大，则将元素值放入第2个位置，否则将元素1先移动到第2个位置，再将下标为0的元素放置在第1个位置。在向数组插入第i+1个元素时，前1到i个元素已经排好序，将插入的值放置在下标为0的位置R【0】，从第i个元素开始依次与R【0】比较，若某位置k元素大于R【0】，那么先将第k到i个元素依次向后移动1位，再将R【0】的值放置在第k个元素位置。重复上面的操作，直到所有的数插入完毕。3.1.3业务实现---直接插入排序3.1.4业务实现---直接插入排序构建直接插入排序结点类：构建直接插入排序结点类：publicclassZj_Node{//用于排序的元素结点

publicintKey;//查找的关键字

publicStudent_infoData;//数据元素(学生信息）

publicZj_Node() { } publicZj_Node(Student_infoelem) { Key=elem.st_yw; Data=elem; }} 3.1.5业务实现---直接插入排序构建直接插入排序业务类：publicclassZj_Sort{publicintMax;//定义常数，记录数据容量大小publicZj_Node[]start;//记录原始的数据publicZj_Node[]end;//记录排序后的新数据publicStudentMangerBa=newStudentManger();//创建数据控制层对象publicZj_Sort() { Init(); }publicvoidInit() {…}//初始化直接查找表 publicvoidSorting(){…}//对学生信息按语文成绩进行排序}

3.1.6业务实现---直接插入排序直接插入排序数据的初始化方法： publicvoidInit() { Max=Ba.Max; start=newZj_Node[Max]; end=newZj_Node[Max+1]; for(inti=0;i<Max;i++) { start[i]=newZj_Node(Ba.base_info[i]); end[i]=newZj_Node(); } end[Max]=newZj_Node(); } 3.1.7业务实现---直接插入排序直接插入排序方法实现：publicvoidSorting(){//直接插入排序inti,j;//定义局部变量用于循环end[0]=start[0];//当插入第一个元素时，认为已经排好序了end[1]=start[0];for(i=1;i<Max;i++)//从原始数据第2个元素起，逐个从中取出元素

{end[0]=start[i];//将取出的元素放入，放入排序数组的第一个元素

j=i;while(end[0].Key<end[j].Key)//从排好序的最后一个元素向前，逐个与待插入的元素进行比较，如果元素比插入元素大

{end[j+1]=end[j]; j--; }end[j+1]=end[0];//将插入元素赋值到对应的位置

}}

算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：0次若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n²)空间复杂度：S(n)=O(1)3.1.8业务实现---直接插入排序3.2.1业务实现---折半插入排序二分插入排序是在直接插入排序基础之上改进的一种排序算法。由于插入排序的操作是在一个有序序列中进行比较和插入的，而比较操作实际上就是在有序序列中作查找操作，这个“查找”操作可以用“二分查找”的方法来实现。按照这种思想，对直接插入排序改进后的排序方法称为二分插入排序，又称为折半插入排序。与直接插入排序相比，二分插入排序仅仅减少了记录关键字的比较次数，而记录的移动次数没有改变。3.2.2业务实现---折半插入排序具体实现的步骤如下：我们用一个一维数组来装载排序好的结果。数组下标为0的元素记录每次要进行插入排序的元素，下标为1、2…N记录已由小到大排好的元素。当向一个数组插入第一个元素时，放置在下标为0和1的位置，这时认为第一个元素已经排好序。在向数组插入第2个元素时，首先放置在下标为0的位置，让它与第1个元素比较，如果比它大，则将元素值放入第2个位置，否则将元素1先移动到第2个位置，在将下标为0的元素放置在第1个位置。在向数组插入第i+1个元素时，前1到i个元素已经排好序，将插入的值放置在下标为0的位置R【0】，从第1个元素到第i个元素，采用二分查找第一个大于R【0】的位置k，那么先将第k到i个元素依次向后移动1为，再将R【0】的值放置在第k个元素位置。重复上面的操作，直到所有的数插入完毕。3.2.3业务实现---折半插入排序3.2.4业务实现---折半插入排序构建折半插入排序结点类：publicclassZb_Node{//用于排序的元素结点

publicintKey;//查找的关键字

publicStudent_infoData;//数据元素(学生信息）

publicZb_Node() { } publicZb_Node(Student_infoelem) { Key=elem.st_yw; Data=elem; }}

3.2.5业务实现---折半插入排序构建折半插入排序业务类：publicclassZb_Sort{publicintMax;//定义常数，记录数据容量大小publicZb_Node[]start;//记录原始的数据publicZb_Node[]end;//记录排序后的新数据 publicStudentMangerBa=newStudentManger();//创建数据控制层对象publicinttimes_all=0;publicZb_Sort() {Max=Ba.Max; start=newZb_Node[Max]; end=newZb_Node[Max+1]; for(inti=0;i<Max;i++) { start[i]=newZb_Node(Ba.base_info[i]); end[i]=newZb_Node(); } end[Max]=newZb_Node();}publicvoidSorting(){…}//对学生信息按语文成绩进行排序}

3.2.6业务实现---折半插入排序折半排序方法实现：publicvoidSorting(){//折半插入排序

inti,j;//定义局部变量用于循环

end[0]=start[0];//当插入第一个元素时，认为已经排好序了

end[1]=start[0];for(i=1;i<Max;i++)//从原始数据第2个元素起，逐个从中取出元素{ intleft=1,right=i; end[0]=start[i]; while(left<=right)//在已排好序的元素中采用二分查找来定位要插入的位置

{ intmiddle=(left+right)/2; if(end[0].Key<end[middle].Key) right=middle-1; else left=middle+1; times_all++; } for(j=i;j>=left;j--)//进行元素的移动

end[j+1]=end[j]; end[left]=end[0];//将插入元素赋值到对应的位置

}}

3.3.1业务实现---冒泡排序算法分析：冒泡排序也称为起泡排序、气泡排序等，是一种简单的、容易理解的排序方法。冒泡排序是通过相邻记录之间的比较和交换使关键字值较小的记录逐渐从底部移向顶部，即从下标较大的单元向下标较小的单元移动，就像气泡从水中不断往上冒。当然，随着关键字较小的记录的逐渐上移，关键字值较大的记录也逐渐下移。3.3.2业务实现---冒泡排序冒泡排序步骤：先将初始记录序列的第n个记录的关键字和第n-1个记录的关键字进行比较，若发现次序相反（即逆序，R[n-1].key>R[n].key），则交换两记录；然后比较第n-1个记录和第n-2个记录，若为逆序，又交换两个记录；如此下去，直到第2个记录和第1个记录的关键字进行比较为止，这样就完成了第一趟冒泡排序。经过第一趟冒泡排序后，关键字最小的记录被放置到R[0]的位置上.然后再进行第二趟冒泡排序，对剩下的n-1个记录再进行类似的操作，其结果是关键字较小的记录被放置到R[1]位置上.重复进行n-1趟后，整个冒泡排序结束。3.3.3业务实现---冒泡排序3.3.4业务实现---冒泡排序构建冒泡排序结点类：publicclassMp_Node{//用于排序的元素结点

publicintKey;//查找的关键字

publicStudent_infoData;//数据元素(学生信息）

publicMp_Node() { } publicMp_Node(Student_infoelem) { Key=elem.st_sx; Data=elem; }}

3.3.5业务实现---冒泡排序构建冒泡排序业务类：publicclassMp_Sort{ publicintMax;//定义常数，记录数据容量大小

publicMp_Node[]start;//记录原始的数据

publicMp_Node[]end;//记录排序后的新数据

publicStudentMangerBa=newStudentManger();//创建数据控制层对象

publicinttimes_all=0; publicMp_Sort() { Max=Ba.Max; start=newMp_Node[Max]; end=newMp_Node[Max+1]; for(inti=0;i<Max;i++) { start[i]=newMp_Node(Ba.base_info[i]); end[i]=newMp_Node(); } } publicvoidSorting(){…}//对学生信息按语文成绩进行排序}

3.3.6业务实现---冒泡排序冒泡排序方法实现：publicvoidSorting() {//冒泡排序 inti,j;//用于循环的局部变量 booleanflag;//用以标志是否排好序 for(i=0;i<Max;i++)//从第一个到最后一个元素进行循环 { flag=true; for(j=Max-2;j>=i;j--)//从最后一个元素到当前元素进行循环获取元素if(start[j+1].Key<start[j].Key)//如果前面一个元素大于后一个元素，交换位置 {end[0]=start[j+1]; start[j+1]=start[j]; start[j]=end[0]; flag=false; times_all++; } if(flag)//如果排好序，退出循环 break; } }算法评价时间复杂度最好情况（正序）比较次数：n-1移动次数：0最坏情况（逆序）比较次数：移动次数：空间复杂度：S(n)=O(1)T(n)=O(n²)3.4.1业务实现---快速排序算法分析：快速排序（QuickSorting）又称为划分交换排序，它是迄今为止所有内排序算法中速度最快的一种。快速排序是对冒泡排序的一种改进。在冒泡排序中，记录的比较和交换是在相邻的单元中进行的，记录每次交换只能上移或下移一个单元，因而总的比较和移动次数较多。而在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较小的记录一次就能从后面单元交换到前面去，而关键字较大的记录一次就能从前面的单元交换到后面的单元，记录每次移动的记录较远，因此可以减少记录总的比较和移动次数。3.4.2业务实现---快速排序快速排序步骤：快速排序的基本做法是：任取待排序的n个记录中的某个记录作为基准（一般选取第一个记录），通过一趟排序，将待排序记录分成左右两个子序列，左子序列记录的关键字均小于或等于该基准记录的关键字，右子序列记录的关键字均大于或等于该基准记录的关键字，从而得到该记录最终排序的位置，然后该记录不再参加排序，此一趟排序称为第一趟快速排序。然后对所分的左右子序列分别重复上述方法，直到所有的记录都处在它们的最终位置，此时排序完成。在快速排序中，有时把待排序序列按照基准记录的关键字分为左右两个子序列的过程称为一次划分。快速排序的过程为：设待排序序列为R[s]到R[t]，其中s为序列的下界，t为序列的上界（），R[s]为该序列的基准记录，为了实现一次划分，可设置两个指针i和j，它们的初值分别为s和t。在划分的过程中，首先让j从其初值开始，依次向前扫描，并将扫描到的每一个记录R[j]的关键字同R[s]（即基准记录）的关键字进行比较，直到R[j].key<R[s].key时，交换R[j]和R[s]的顺序，使得关键字比基准记录关键字小的记录交换到左边的子序列中；然后让i从i+1开始，依次向后扫描，并将扫描到的每一个记录R[i]的关键字同R[j]的关键字（此时R[j]作为基准记录）进行比较，直到R[i].key>R[j].key时交换R[i]和R[j]的顺序，使关键字大的记录交换到右边的子序列中；再接着让j从j-1开始，依次向前扫描。重复上述过程，如此交替改变扫描方向，从两端各自向中间位置靠拢，直到i等于j。经过此次划分后得到的左右两个子序列分别为R[s]……R[i-1]和R[i+1]……R[t]，依此类推。3.4.3业务实现---快速排序3.4.4业务实现---快速排序构建快速排序结点类：publicclassQk_Node{//用于排序的元素结点

publicintKey;//查找的关键字

publicStudent_infoData;//数据元素(学生信息）

publicQk_Node() { } publicQk_Node(Student_infoelem) { Key=elem.st_yw; Data=elem; }}

3.4.5业务实现---快速排序构建快速排序业务类：publicclassQk_Sort{ publicintMax;//定义常数，记录数据容量大小

publicQk_Node[]start;//记录原始的数据

publicStudentMangerBa=newStudentManger();//创建数据控制层对象

publicinttimes_all=0; publicQk_Sort() { Max=Ba.Max; start=newQk_Node[Max]; for(inti=0;i<Max;i++) { start[i]=newQk_Node(Ba.base_info[i]); } } public voidSorting(intlow,inthigh){…}//对学生信息按语文成绩进行排序}

3.4.6业务实现---快速排序快速排序方法实现：public voidSorting(intlow,inthigh){//快速排序low排序下限，high排序上限inti=low,j=high;Qk_Nodetemp=start[low];//快速排序的支点while(i<j){while((start[j].Key>=temp.Key)&&(i<j))//从表的末端向前收索与支点比较

{j--; times_all++; }if(j>i)//末端的元素比支点小，发生交换

{start[i]=start[j]; i++; }while((start[i].Key<=temp.Key)&&(i<j))//从表的前端向后收索与支点进行比较

{ times_all++; i++; }if(j>i)//前端的元素比支点大，发生交换

{ start[j]=start[i]; j--; } } start[i]=temp;//将支点记录移到新位置

if(low<(i-1))Sorting(low,i-1);//递归调用左半区排序

if(high>(i+1))Sorting(i+1,high);//递归调用右半区排序}

例初始关键字：4938659776132750ijxji

完成一趟排序：(273813)49(76976550)分别进行快速排序：(13)27(38)49(5065)76(97)快速排序结束：13273849

506576974927ijijij4965ji1349ij4997ij算法评价时间复杂度最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)空间复杂度：需栈空间以实现递归最坏情况：S(n)=O(n)一般情况：S(n)=O(log2n)T(n)=O(n²)3.5.1业务实现---选择排序直接选择排序是一种简单的排序方法。它每次从待排序的记录序列中选取关键字最小的记录，把它同当前记录序列中的第一个记录相交换位置。具体的作法是：开始时待排序序列为R[0]……R[n-1]，经过选择和交换后，R[0]中存放最小关键字的记录；第二次待排序记录序列为R[1]……R[n-1]，经过选择和交换后，R[1]为仅次于R[0]的具有次小关键字的记录；如此类推，经过n-1次选择和交换之后，R[0]……R[n-1]成为有序序列，即可实现排序。3.5.2业务实现---选择排序3.5.3业务实现---选择排序构建选择排序结点类：publicclassSe_Node{//用于排序的元素结点

publicintKey;//查找的关键字

publicStudent_infoData;//数据元素(学生信息）

publicSe_Node() { } publicSe_Node(Student_infoelem) { Key=elem.st_yw; Data=elem; }}

3.5.4业务实现---选择排序构建选择排序业务类：publicclassSelect_Sort{ publicintMax;//定义常数，记录数据容量大小 publicSe_Node[]start;//记录原始的数据 publicStudentMangerBa=newStudentManger();//创建数据控制层对象 publicinttimes_all=0; publicSelect_Sort(){ Max=Ba.Max; start=newSe_Node[Max]; for(inti=0;i<Max;i++) { start[i]=newSe_Node(Ba.base_info[i]); } } publicvoidSorting(){…}//对学生信息按语文成绩进行排序}3.5.5业务实现---选择排序选择排序方法实现