数据结构第二十一讲.ppt

《数据结构第二十一讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第二十一讲1交换排序2选择排序110.3交换排序利用交换记录的位置进行排序的方法称为交换排序。其基本思想是：两两比较待排序记录的关键字，如果逆序就进行交换，直到所有记录都排好序为止。常用的交换排序方法主要有冒泡排序和快速排序。快速排序是一种分区交换排序法，是对冒泡排序方法的改进。2冒泡排序（Bubblesort）的算法思想是：设待排序有n个记录，首先将第一个记录的关键字R1.key和第二个记录的关键字R2.key进行比较，若R1.key>R2.key，就交换记录R1和R2在序列中的位置；然后继续对R2.key和R3.key进行比较，并作相同的处理；重复此过程，直到关键字Rn-1.k

2、ey和Rn.key比较完成。其结果是n个记录中关键字最大的记录被交换到序列的最后一个记录的位置上，即具有最大关键字的记录被“沉”到了最后，这个过程被称为一趟冒泡排序。然后进行第二趟冒泡排序，对序列表中前n-1个记录进行同样的操作，使序列表中关键字次大的记录被交换到序列的n-1位置上；第i趟冒泡排序是从R1到Rn-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关10.3.1冒泡排序3键字最大的记录被交换到n-i+1位置上。每一趟排序都有一个相对大的数据被交换到后面，就像一块块“大”石头不断往下沉，最大的总是最早沉下；而具有较小关键字的记录

3、则不断向上（前）移动位置，就像水中的气泡逐渐向上飘浮一样，冒到最上面的是关键字值最小的记录。所以把这种排序方法称为冒泡排序。对有n个记录的序列最多做n-1趟冒泡就会把所有记录依关键字大小排好序。如果在某一趟排序中都没有发生相邻记录的交换，表示在该趟之前已达到排序的目的，整个排序过程可以结束。在操作实现时，常用一个标志位flag标示在第i趟是否发生了交换，若在第i趟发生过交换，则置flag=false（或0）；若第i趟没有发生交换，则置flag=true（或1），表示在第i-1趟已经达到排序目的，可结束整个排序过程。4算法描述如下：#defineFalse0#defineTrue1t

4、ypedefintkeytype;voidBubble_Sort(RecTypeR[],intn)//用冒泡排序对R[1]~R[n]记录排序{inti,j,flag=0;for(i=1;i

5、排序的执行趟数，内层循环用于控制在一趟冒泡排序中相邻记录间的比较和交换。【例10-4】假设有8个记录，关键字分别为53，38，47，24，69，05，17，38，用冒泡排序方法排序。【解】冒泡排序过程如图10-4所示。6图10-4冒泡排序过程7执行了5趟冒泡排序后，完成了整个排序过程。排序中当关键字间的比较呈逆序时，需要交换两个记录的位置，使用一个辅助空间来完成交换。在算法中用数组中的R[0]作为辅助空间，所以其空间复杂度为O(1)。对于有n个记录的待排序列进行冒泡排序，算法的时间复杂度依赖于待排序序列的初始特性，有以下几种情况：（1）如果初始记录序列为“正序”序列，则只需进行一趟

6、排序，记录移动次数为0，关键字间比较次数为n-1；8（2）如果初始记录序列为“逆序”序列，则进行n-1趟排序，每一趟中的比较和交换次数将达到最大，即冒泡排序的最大比较次数为=n(n-1)/2，最大移动次数为3×=3n(n-1)/2。（3）一般情况下，比较次数≤n(n-1)/2，移动次数≤3n(n-1)/2，因此时间复杂度为O(n2)。由相邻两个记录的交换条件可知冒泡排序是稳定排序。910.3.3快速排序快速排序（QuickSorting）又称分区交换排序，是对冒泡排序算法的改进，是一种基于分组进行互换的排序方法。1．快速排序的基本思想快速排序的基本思想是：从待排记录序列中任取一个记

7、录Ri作为基准（通常取序列中的第一个记录），将所有记录分成两个序列分组，使排在Ri之前的序列分组的记录关键字都小于等于基准记录的关键字值Ri.key，排在Ri之后的序列分组的记录关键字都大于Ri.key，形成以Ri为分界的两个分组，此时基准记录Ri的位置就是它的最终排序位置。此趟排序称为第一趟快速排序。然后分别对两个序列分组重复上述过程，直到所有记录排在相应的位置上。102．选取基准在快速排序中，选取基准常用的方法有：（1）选取序列中第一个记录的关键字值作为基准关键字