《第13周内排序第3讲-交换排序.pdf》由会员分享，可在线阅读，更多相关《第13周内排序第3讲-交换排序.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、常见的交换排序方法：常见的交换排序方法： （1）冒泡排序（或起泡排序）冒泡排序（或起泡排序） （2）快速排序）快速排序 两个记录反两个记录反序时进行交换序时进行交换 基本思路基本思路 有 序 区 有 序 区 R0 Ri- -1 无 序 区 无 序 区 Ri Ri+1 Rn-1 将无序区中将无序区中 最小记录放最小记录放 在在Ri 有 序 区 有 序 区 R0 Ri- -1 Ri 无 序 区 无 序 区 Ri+1 Rn- -1 一趟排序一趟排序 初始有序区为空初始有序区为空。 i0n- -2，共，共n- -1趟使整个数据有序。趟使整个数据有序。 有序区有序区总是全总是全 局有序的局有序的 voi
2、d BubbleSort(RecType R,int n) int i,j; RecType temp; for (i=0;ii;j-)/比较找本趟最小关键字的记录比较找本趟最小关键字的记录 if (Rj.keyRj-1.key) temp=Rj;/RjRj-1 Rj=Rj-1; Rj-1=temp; 冒泡排序算法冒泡排序算法 采用前面的冒泡排序方法对采用前面的冒泡排序方法对(2,1,3,4,5) 进行排序进行排序 初始关键字初始关键字21345 12345i=0 12345i=1 12345i=2 12345i=3 已经全部有已经全部有 序了序了 一旦一旦某一趟比较时不出现记录交换，说明已排
3、好序了某一趟比较时不出现记录交换，说明已排好序了，就可，就可 以结束本算法。以结束本算法。 如何提高效率？如何提高效率？ void BubbleSort(RecType R,int n) int i, j; bool exchange; RecType temp; for (i=0;ii;j-)/比较比较,找出最小关键字的记录找出最小关键字的记录 if (Rj.keyRj-1.key) temp=Rj; Rj=Rj-1; Rj-1=temp; exchange=true; if (exchange=false) return; /中途结束算法中途结束算法 改进冒泡排序改进冒泡排序算法：算法：
4、最好最好的情况（关键字在记录序列的情况（关键字在记录序列中正序中正序）：只需：只需进行一趟冒泡进行一趟冒泡 最坏最坏的情况（关键字在记录序列的情况（关键字在记录序列中反序中反序）：需：需进行进行n- -1趟冒泡趟冒泡 0 “移动”“移动”的次数：的次数：“比较”“比较”的次数：的次数： n- -1 “比较”“比较”的次数：的次数： 2 )1( )1( 1 0 nn in n i “移动”“移动”的次数：的次数： 2 )1(3 )1(3 2 0 nn in n i 所以冒泡排序最好时间复杂度为所以冒泡排序最好时间复杂度为O(n)，最坏和平均为，最坏和平均为O(n2)。 算法分析算法分析 无无 序
5、序 的的 记记 录录 序序 列列 无序子序列无序子序列无序无序子子序列序列基准基准 一次划分一次划分 分别进行快速排序分别进行快速排序 每每趟使表的趟使表的第第1个个元素元素放入放入适当适当位置位置（归位归位），将表一分为二将表一分为二，对对 子表按递归方式继续这种划分子表按递归方式继续这种划分，直至划分的子表长直至划分的子表长为为0或或1（递归出递归出 口口）。 基准基准 31542 回顾划分：示例回顾划分：示例 tmp ij i=j：区间处理完毕：区间处理完毕 划分完毕划分完毕 整个区间：整个区间：Rs.t 左区间：左区间：Rs.i- -1右区间：右区间：Ri+1.t void Quick
6、Sort(RecType R,int s,int t) /对对Rs至至Rt的元素进行快速排序的元素进行快速排序 int i=s,j=t; RecType tmp; if (si Ri=Rj; while (ij Rj=Ri; Ri=tmp; QuickSort(R,s,i-1);/对左区间递归排序对左区间递归排序 QuickSort(R,i+1,t);/对右区间递归排序对右区间递归排序 /递归出口：不需要任何操作递归出口：不需要任何操作 快速排序算法快速排序算法 一次划分 【例例10- -2】设待排序的表有设待排序的表有10个个记录记录，其其关键字分别为关键字分别为6，8，7， 9，0，1，3
7、，2，4，5。说明说明采用快速采用快速排序方法进行排序的过程排序方法进行排序的过程。 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 19 7 86 1 4 2 3 05 0，1，2，3，4，5，6，7，8，9 02341 342 34 8 79 78 快速排序递归树快速排序递归树 将递归树看成一颗将递归树看成一颗3叉树，叉树， 每个分支节点对应一次递归每个分支节点对应一次递归 调用。这里递归次数：调用。这里递归次数：7 左右分区处理的顺序无关左右分区处理的顺序无关 【例例10- -3】采用递归方式对顺序表进行快速排序，下列关于递采用递归方式对顺序表进行快速排序，下列关于递 归次数
8、的叙述中，正确的是归次数的叙述中，正确的是。 A. 递归次数与初始数据的排列次序无关递归次数与初始数据的排列次序无关 B. 每次划分后，先处理较长的分区可以减少递归次数每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区处理顺序无关递归次数与每次划分后得到的分区处理顺序无关 说明：本题为说明：本题为2010年全国考研题年全国考研题 【例例10- -4】 为实现快速排序法，待排序序列宜采用存储方式为实现快速排序法，待排序序列宜采用存储方式 是是。 A. 顺序顺序存储存储B
9、. 散列存储散列存储 C. 链式存储链式存储D. 索引存储索引存储 说明：本题为说明：本题为2011年年全国考研题全国考研题 最好最好情况：情况： n个元素个元素 log2n 层层 此时时间复杂度为此时时间复杂度为O(nlog2n)，空间复杂度为，空间复杂度为O(log2n)。 n/2或或n/2 - -1个个元素元素 算法分析算法分析 n/2或或n/2- -1个个元素元素 划分时间为划分时间为O(n) 最坏最坏情况：情况： n个元素个元素 n- -1个元素个元素 n- -2个元素个元素 n层层 此时时间复杂度为此时时间复杂度为O(n2)，空间复杂度为，空间复杂度为O(n)。 划分时间为划分时间为O(n) 结论结论: : 快速快速排序排序的平均时间的平均时间复杂度为复杂度为O(nlog2n) 。 平均所需栈空间为平均所需栈空间为O(log2n)。 1次划分的时间次划分的时间 则可得结果：则可得结果： Tavg(n)=Cnlog2n。 n个元素个元素 k- -1个元素个元素n- -k个元素个元素 k：1n，共有共有n种情况种情况 n k avgavgavg knTkT n CnnT 1 )()1( 1 )( 由此可得快速排序所需时间的平均值为：由此可得快速排序所需时间的平均值为： 平均平均情况：情况： 划分时间为划分时间为O(n) 本讲完本讲完