文档介绍：第六章排序 1. 掌握典型的交换排序算法和选择排序的算法; 2. 了解各种算法的优缺点和适用范围。 3 .学会合理的设计算法。?教学重点: 交换排序算法和选择排序的算法?教学难点: 交换排序算法和选择排序的算法的设计?授课内容 交换排序 1 .冒泡排序冒泡排序( Bubble sort ) 是一种人们熟悉的、最直观的交换排序方法。在排序过程中,从上到下对每两个相邻记录比较关键字大小,使较小关键字的记录上升,像水中的气泡向上冒出一样,而关键字较大的记录好比石头沉到序列的底部,故称此方法为冒泡排序法。算法思路: 若有 n 个记录需要排序, 首先将第一个记录的关键字和第二个记录的关键字进行比较, 若为逆序(即 r[2].key<r[1].key ), 则两个记录交换, 然后比较第二个记录和第三个记录的关键字。依此类推,直至第 n 个记录和第 n-1 个记录的关键字进行比较/ 交换为止。 void BubbleSort (RcdType r[ ],int n){ for(i=1;j<n;i++){ flag=1; for(j=1;j<=n-i;j++) if(r[j+1].key<r[j].key){ flag=0; r[0]=r[j];r[j]=r[j+1];r[j+1]=r[0]; } if(flag) break; 第二十二讲内部排序(二) 第六章排序}}2 .快速排序快速排序( Quick sort ) 是由霍尔( Hoare ) 提出,它是一种对冒泡排序的改进。该方法的实质是将一组关键字[K 1 ,K 2 ,K 3,…,Kn] 进行分区交换排序。通过一趟排序将待排序的记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行分区交换排序,以达到整个序列有序。算法思路是: (1) 任选一个关键字(一般可先第一记录的关键字 K 1 )为控制字,将[K 1 ,K 2,…,Kn] 分成左、右两个子区, 使左区所有关键字小于等于 K 1, 右区所有关键字大于等于 K 1, 最后控制字 K 1 居两个子区中间的适当位置。在子区内数据尚处于无序状态。(2) 将右区首、尾指针[ 记录的下标号] 保存入栈, 对左区进行与第(1) 步相类似的操作,又得到它的左子区和右子区,控制字居中。(1) 重复第( 1 )、( 2 )步,直到左区处理完毕。然后退栈,再对另一个子区进行相类同的处理,直到栈空。第六章排序 void Quick_Sort(RcdType r[ ],int low,int high){ i=low;j=high;t=r[low]; while(i<j){ while(i<j&&r[j].key>t..key) j--; if(i<j) r[i++]=r[j]; while(i<j&&r[i].key<=) i++; if(i<j) r[j--]=r[i]; } if(low<i-1) Quick_Sort(r,low,i-1); if(high>i-1) Quick_Sort(r,i+1,high); 第六章排序} 选择排序选择排序( Selection sort ) 是以选择为基础的一种常用排序方法, 它也有几种不同的实现方法,这里仅介绍单选择排序和堆排序。 1. 简单选择排