数据结构（Java语言版）课件 第十章 排序

数据结构（Java语言版）10排序【知识目标】²

掌握插入排序中直接插入排序和希尔排序的思想及实现；²

掌握交换排序中冒泡排序和快速排序的思想及实现；²

掌握选择排序中直接选择排序和堆排序方法的思想及实现；²

掌握归并排序的思想及实现；²

理解基数排序的思想及实现。【能力目标】²

具备熟练利用各种排序方法编写相应程序代码的能力；²

能够针对不同的应用选用合适的排序算法解决实际应用问题；²

具有比较各种排序方法、分析其算法的时间复杂度及空间复杂度的能力。实例引入学号姓名数学语文历史地理体育英语政治总分1王学亮788987899085866042彭飞907067758086955633李丽878078868595835944张月梦676698859032865245李雪菲988983838675876016王佳佳907762868585835687田悦悦855690958090825788张亮739089979082926139张雪燕7887878575758056710李飞89678889807683572排序：对于需要整理的文件或者相关数据，使之按某个类别的数据元素（或者数据项）的递增或递减次序排列起来的过程。记录：在排序中对应的数据元素被称为“记录”（或称为“元素”），记录可以由单个数据构成，也可以由一组数据构成，记录的集合称为“文件”（或称为“序列”），有时在内存中的文件也常被称为“表”。排序的概念关键字：对于由n个记录构成的序列{R1,R2,…,Rn}，其中Ki为排序时所依据的数据项，称其为关键字，关键字序列可记为{K1,K2,…,Kn}。排序还可以描述成对于需要整理的文件或者相关数据，使其在关键字关系Ki1≤Ki2≤…≤Kin（或者Ki1≥Ki2≥…≥Kin）下得到序列（Ri1,Ri2,…,Rin）的过程。排序的概念按照存储交换分类可将排序划分为内部排序和外部排序。排序按照内部排序的过程分类，可划分为4类，即插入排序、交换排序、选择排序，以及其他排序。排序按照稳定性分类可划分为稳定排序和不稳定排序。排序的分类插入排序-直接插入排序直接插入排序是指每次将一个记录插入已经排好序的序列中，直到结束为止。【基本思想】设1≤i≤n，已知文件或者相关数据中的记录{R1,R2,…,Ri−1}已经是按照关键字K1≤K2≤…≤Ki−1（或者K1≥K2≥…≥Ki−1）排成的一个有序序列，现将下一个待排序记录Ri插入{R1,R2,…,Ri−1}中，使其仍然满足有序的过程，就是插入排序。算法publicvoidinsertSort(int[]a) {intt;for(inti=1;i<a.length;i++){t=a[i];intj=i-1;while(j>=0){ //为每个待插入元素寻找插入位置if(t<a[j]) //发现插入位置后，执行元素移动a[j+1]=a[j]; //移动元素else //如果a[i]>a[j]，则退出内循环break;j--;}a[j+1]=t; //将待插入元素放到合适的位置}}算法分析

直接插入排序的实现是通过对记录比较和移动的方式进行的，其算法的时间复杂度为O(n2)，n为数据个数。当待排序的数据量非常大时，其算法的时间复杂度也比较高。希尔排序算法描述先将待排序记录分成若干个组，在每个组内进行直接插入排序，然后将划分的组逐步变大直到包含全部记录为止。其过程如下：①取一个小于序列记录个数n的整数d1作为第一个增量，把全部数据分成若干组，将所有距离为dl倍数的数据分在同一个组中。先在各组内进行直接插入排序；②取第二个增量d2<d1，重复上述分组和排序；③直至所取的增量di=1（di<di-l<…<d2<d1），即将所有数据放在同一组中进行直接插入排序。希尔排序publicvoidshellOne(Comparable[]a,intd){

intt;

intn=a.length;

intj=0;

for(inti=d;i<n;i++){ //对每组子序列执行插入操作if(a[i].compareTo(a[i-d])<0){t=a[i];j=i-d;do{ //查找a[i]的插入位置a[j+d]=a[j]; //后移记录j=j-d; //查找下一个记录}while(j>0&&pareTo(a[j])<0);a[j+d]=t; //将a[i]放到正确的位置上}

}}

publicvoidshellSort(Comparable[]a){

intincr=a.length;

do{incr=incr/2; //求下一增量，在这里增量通过除以2获得shellOne(a,incr); //一次增量为incr的希尔排序

}while(incr>=1);}算法分析

希尔排序的执行时间取决于增量序列，希尔排序增量序列的选择具有如下共同的特征：①最后一个增量必须为1，增量的取值一般不取2的倍数或者整数次幂的形式；②应该尽量避免序列中的值（尤其是相邻的值）互为倍数的情况；③希尔排序的性能分析过程比较复杂，经过大量实验得出，其算法的时间复杂度为O(n3/2)。。交换排序-冒泡排序算法描述冒泡排序是一种简单的交换排序，其排序过程：对相邻的记录按关键字进行大小比较，如果满足排序要求，则不进行交换，否则将两个记录交换。publicvoidbubble(Comparable[]a){Comparablet; //交换时使用的临时变量intn=a.length; //获取记录个数booleanflag; //flag标记是否有交换发生for(inti=1;i<n-1;i++){ //n个记录最多需进行n-1次排序flag=false; //假设没有发生交换for(intj=0;j<=n–i;j++){ //执行冒泡排序if(a[j].compareTo(a[j+1])>0){ //调用比较方法进行比较t=a[j]; //交换记录位置a[j]=a[j+1];a[j+1]=t;flag=true;}}if(!flag){ //如果没有发生交换，排序结束break;}}}冒泡排序算法分析冒泡排序是一种基于相邻元素之间位置交换的排序方法，是一种稳定的排序方法。其算法的时间复杂度与待排序序列的初始状态有直接关系，其平均时间复杂度为O(n2)，n为待排序元素的个数。快速排序

快速排序（QuickSort）是另一种交换排序，又称为分区交换排序，是对冒泡排序的改进。【基本思想（以升序为例）】在待排序的n个记录中任取一个记录（一般取第一个记录），以该记录作为排序的枢轴记录，将所有记录分为两组（这两组内部一般都是无序的），对于比枢轴记录关键字的值小或者相等的记录，将其放在枢轴记录的左边一组，对于比枢轴记录关键字大的记录放在枢轴记录的右边一组，称此为一次快速排序，对得到的两组记录分别重复上述的操作，直到完成整个排序过程。快速排序publicvoidquick(Comparable[]c,intstart,intend){Comparabletmp=c[start]; //暂存枢轴记录intn=end-start+1; //参与排序的记录个数inti=start,j=end;while(i<j){while(c[j].compareTo(tmp)>0&&i<j){ //从j开始搜索小于枢轴记录关键字的值j--;}if(i<j){ //出现小于枢轴记录关键字的值后，将j对应的值放到i位置处c[i]=c[j];i++;}while(c[i].compareTo(tmp)<=0&&i<j){//从i向后搜索，找出大于枢轴记录关键字的值i++;}if(i<j){ //出现大于枢轴记录关键字的值后，将i处的值放入j处c[j]=c[i];j--;}}c[i]=tmp; //完成一次搜索后，把枢轴记录值放在合适位置if(start<i–1)quick(c,start,i-1); //递归调用，对左子序列进行快速排序if(end>i+1)quick(c,i+1,end); //递归调用，对右子序列进行快速排序}快速排序算法分析

从快速排序算法程度的递归过程可知，快速排序的次数取决于递归的深度。最好的情况下，算法时间复杂度为O(nlog2n)；最坏情况下，快速排序的速度退化到简单排序水平，算法的时间复杂度为O(n2)。快速排序的特点：①记录的非顺序移动导致排序不稳定；②快速排序适用于顺序结构；③当记录数较大时，在一般情况下快速排序是内部排序方法中速度最快的一种。选择排序基本思想：对待排序序列{a1,a2,…,an}进行n次选择操作，其中第i次操作是选择第i个关键字较小（或较大）的记录，并将其放在第i个（或(n-i+1)个）记录的位置上，该排序通过比较选择需要交换的记录，对其进行记录位置的交换。选择排序包括直接选择排序和堆排序。直接选择排序基本思想：对于具有n个记录的待排序序列，以升序为例，其直接选择排序的步骤如下：①从待排序序列中，找到关键字值最小的记录；②如果关键字值最小的记录不是第一个，把关键字值最小的记录与第一个记录交换；③从余下的(n-1)个记录中，找出关键字值最小的记录与第二个记录交换，重复步骤①、②，直到排序结束。直接选择排序经过(n-1)次排序后将得到整个序列的有序序列。publicvoidselectSort(Comparable[]c) {Comparablemin,t; //最小记录临时存储变量minintmIndex=0; //记录最小记录的当前位置索引

intn=c.length;for(inti=0;i<n;i++){ //n个记录进行n-1次排序

min=c[i]; //假设第i个记录为最小记录并暂存

mIndex=i;for(intj=i+1;j<n;j++){ //在之后的记录中查找最小记录

if(c[j].compareTo(min)<0){min=c[j];mIndex=j;}}if(mIndex!=i){ //最小记录如果不在i处，则进行交换

t=c[i];c[i]=c[mIndex];c[mIndex]=t;}}}直接选择排序算法分析【性能分析】直接选择排序通过增加比较次数来减少记录移动的次数，其算法的时间复杂度为O(n2)，n为待排序记录的个数。堆排序堆的定义：对于具有n个元素的待排序序列{R1,R,…,Rn}，关键字序列为{K1,K2,…,Kn}，当且仅当满足下列条件之一时，该序列被称为堆。①Ki≤K2i（2i≤n），且Ki≤K2i+1（2i+1≤n）；②Ki≥K2i（2i≤n），且Ki≥K2i+1（2i+1≤n）。当一个序列满足条件①时，称为小根堆，适合从小到大的排序；满足条件②时，称为大根堆，适合从大到小的排序。堆排序【基本思想】利用小根堆（或大根堆）来选取当前无序序列中关键字值最小（或最大）的记录来排序。以大根堆排序为例，堆排序的过程如下。（1）建立一个堆结构按照堆定义中给出的条件②，先选取i=n/2（第n个节点的双亲节点的编号），把