(25)--第7章 排序-交换类数据结构.ppt
《(25)--第7章 排序-交换类数据结构.ppt》由会员分享,可在线阅读,更多相关《(25)--第7章 排序-交换类数据结构.ppt(41页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第8章 排序交换类排序基本思想:两两比较,如果发生逆序则交换,直到所有记录都排好序为止。起泡排序O(n2)快速排序O(nlog2n)8.3交换排序基本思想:每趟不断将记录两两比较,并按“前小后大”规则交换21,25,49,25*,16,0821,25,25*,16,08,4921,25,16,08,25*,4921,16,08,25,25*,4916,08,21,25,25*,4908,16,21,25,25*,49冒泡排序 void bubble_sort(SqList&L)int m,i,j,flag=1;RedType x;m=n-1;while(m0)&(flag=1)flag=0;f
2、or(j=1;jL.rj+1.key)flag=1;x=L.rj;L.rj=L.rj+1;L.rj+1=x;/交换 /endif m-;/endwhile 算法描述设对象个数为设对象个数为n n比较次数和和移动次数与初始排列有关与初始排列有关只需 1趟排序,比较次数为 n-1,不移动 21212525494925*25*16160808最好情况下:排序性能分析21212525494925*25*16160808需 n-1趟排序,第i趟比较n-i次,移动3(n-i)次最坏情况下:排序性能分析与初序有关时间复杂度为 O(n2)空间复杂度为 O(1)是一种稳定的排序方法排序性能分析对n个不同的关键字
3、由小到大进行冒泡排序,在下列()情况下比较的次数最多。从小到大排列好的从大到小排列好的元素无序元素基本有序ABCD提交单选题2分基本思想:任取一个元素(如第一个)为枢轴所有比它小的元素一律前放,比它大的元素一律后放,形成左右两个子表;对各子表重新选择枢轴元素并依此规则调整,直到每个子表的元素只剩一个,或空表为止快速排序21212525494925*25*161608080 1 2 3 4 5212125*25*16162525161608084949pivotkeypivotkey080821210808161625*25*2121pivotpivotkeykeypivotpivotkeyke
4、y25*25*2525494925254949pivotpivotkeykey49490808161625*25*25252121如果待排序列中有两条记录或以上1.找到枢轴记录的最终位置(一趟划分)2.对前部分进行快速排序3.对后部分进行快速排序快速排序思路0 1 2 3 4 5 6 7 84938659776132765*38659776132765*highlow49一趟划分49high27low low65high13low97highhigh49int Partition(SqList&L,int low,int high)L.r0=L.rlow;pivotkey=L.rlow.key
5、;while (low high)while(low=pivotkey)-high;L.rlow=L.rhigh;while(low high&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rlow=L.r0;return low;一趟划分算法一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为()。(38,40,46,56,79,84)(40,38,46,79,56,84)(40,38,46,56,79,84)(40,38,46,84,56,79)ABCD提交单选题2分某整形数组A的十个元
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 25-第7章 排序-交换类数据结构 25 排序 交换 数据结构
限制150内