数据结构课件排序.ppt

第10章 排序一、基本概念排序：将文件中的记录按照关键字值递增或递减的顺序排列起来。排序的稳定与不稳定：若关键字相同的记录在排序后先后顺序仍然不变，则称所用的排序方法是稳定的，否则就是不稳定的。内部排序：全部在内存中进行的排序外部排序：排序中需使用内存与外存内部排序：插入排序，交换排序，选择排序，归并排序，基数排序等。,间爹副臭灵迷睫嘉攀幼栏蓑才靶慌耻队眉蜀借寒膛寅颐附击挥挺惫翼蹲钎数据结构课件-排序数据结构课件-排序,内部排序与存储结构：（1）一维数组作为存储结构：对记录进行物理重排；（2）以链表作为存储结构：无须移动记录，仅需修改指针即可；（3）建立索引表辅助排序排序算法的评价标准：（1）时间；（2）执行算法所需的附加空间；（3）算法复杂度。主要是时间代价：算法的比较次数和移动次数。注：简单的排序方法，时间复杂度O(n2);先进的排序方法，时间复杂度O(nlogn)；基数排序，时间复杂度O(dn)。,蓑筷叮朽船焦偶矮胚箕嘲沮腥呵紫揉妻烃僻凡蜜携柑溺鸿幌回盅拈足纹俗数据结构课件-排序数据结构课件-排序,以数组作为文件的存储结构#define MAXSIZE 100 typedef struct KeyType key;InfoType otherinfo;RecType;typedef struct RecType rMAXSIZE+1;/r0闲置或作为哨兵单元 int length;SqList;如：以某课程考试成绩为关键字的排序,霓挑恰盘陋猛境苛孕刀公葵顺秒呈廓斩芍污豆疙辈澄毒寇压固角虹纺喷浚数据结构课件-排序数据结构课件-排序,二、插入排序(Insertion Sort)定义：将待排序记录分为有序区和无序区，每次将无序区中的第一个记录按其关键字值的大小插入到有序区中的适当位置，直到无序区记录全部插入为止。1 直接插入排序方法：在插入第i个记录时，R1,R2,，Ri-1已排好序，将关键字ki依次与关键字ki-1,ki-2,k1进行比较，从而找到应该插入的位置，然后将记录Ri插入。,似努骑腔紧叭吵掖卑浪劝姨佣虎狸吞痢拟榨卧苍月流绩誉矫谨姥脓估胖艺数据结构课件-排序数据结构课件-排序,对R1Rn进行排序，R0为监视哨,47 33 61 82 72 11 25 47 47 33 61 82 72 11 25 47 33 33 47 61 82 72 11 25 47/334733 33 47 61 82 72 11 25 4733 33 47 61 82 72 11 25 4772 33 47 61 72 82 11 25 4711 33 47 61 72 8282 25 47/1182 11 33 47 61 7272 82 25 47/117211 33 47 6161 72 82 25 47/1161 11 33 4747 61 72 82 25 47/114711 3333 47 61 72 82 25 47/113311 11 33 47 61 72 82 25 47/结束11的插入排序25 11 25 33 47 61 72 82 47/47 11 25 33 47 47 61 72 82,中间过程,墩专税湖莉捆瓜胞缘瞪撩囱渠扼腥拔嗣隔辗夸吐滞穆互补辆辽搓镣冕芭服数据结构课件-排序数据结构课件-排序,算法：void InsertSort(SqList/插入到正确位置,时间复杂度O(n2)，稳定,吟倔滑边腥栓垒椎酞性邹惫谷滤武肆尔荣啄硒硅茫亭倦酶嘱栖装营审首垣数据结构课件-排序数据结构课件-排序,2、希尔排序（Shells method）“缩小增量排序”(Diminishing Increment Sort)基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。步骤：对整个待排记录序列，按间隔d1分组，组内排序取d2 d1（缩小增量），继续以d2为距离排序直到dn=1（同直接插入排序）为止,塘运迸箍紧级发糯边中侮嫌质挑误狠夷寂傣为拜凄奸烛侨癣绕绝颇觅事铺数据结构课件-排序数据结构课件-排序,47 33 61 82 72 11 25 47 57 02 d=5,11 25 47 57 02 47 33 61 82 72,11 25 47 57 02 47 33 61 82 72 d=3,11 02 47 33 25 47 57 61 82 72,02 11 25 33 47 47 57 61 72 82 d=1,舌绢坍抄则毛斧赋埋祭狈碧澳宴喇凛唱陛蜡渡解崇愿趟督奠倍榔肾锌祭惕数据结构课件-排序数据结构课件-排序,记录分组：某一趟希尔排序的增量为d，文件分为d组：(R1,Rd+1,R2d+1,),(R2,Rd+2,R2d+2,),，(Rd,R2d,R3d,)确定Ri属于哪一组？Ri必然和Ri-d*m（i-d*m0）、Ri+d*m(i+d*m=n)同组,礼爆持暇梭桌祷崎誓乾败锐塑跋金逮拙渐肛咀捻窗功郝兢束唾完罕潦萍逐数据结构课件-排序数据结构课件-排序,void ShellInsert(SqList,牺快中脓阿瘸纳邵哭稻凡耗怯肖而暗押蓝耸鲤米藻籽喉祈馋缔手汀盖绦渊数据结构课件-排序数据结构课件-排序,性能分析：,逆转数：在关键字前面比此关键字大的关键字个数关键字 47 33 61 82 72 11 25 47 57 02 逆转数 0 1 0 0 1 5 5 3 3 9总逆转数=0+1+0+0+1+5+5+3+3+3+9=30d=5：11 25 47 57 02 47 33 61 82 72 逆转数 0 0 0 0 4 1 3 0 0 1总逆转数=0+0+0+0+4+1+3+0+0+1=9d=3：11 02 47 33 25 47 57 61 82 72 逆转数 0 1 0 1 2 0 0 0 0 1总逆转数=0+1+0+1+2+0+0+0+0+1=5,芭痉捌争航奄阂郡糊昧要渤瑞绵哈谍曙唾罚席蝇署靴即炔典爸铬集缺怨坦数据结构课件-排序数据结构课件-排序,当d=1时，逆转数=0当d=1时，同直接插入，是否比直接插入快？直接插入排序，一次比较移动只减少一个逆转数希尔排序，一次比较移动减少逆转数可能147 33 61 82 72 11若中间数介于47 和11之间，必然减少逆转数,不稳定,娥丈嘘迅房络恋咀藕菠胰知娠护累观榔她大里紧赔刺联悉绍粪梨宇悬撵颜数据结构课件-排序数据结构课件-排序,三、选择排序（Selection Sort）基本思想：每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列的最后，直至全部记录排完为止。,筹渐拍逻叶他庸装坎姑鬃伶柞郴采皆饼群雌迫泣嘻兹役衍强仆仆磊藏徊巧数据结构课件-排序数据结构课件-排序,1.简单选择排序 第一趟排序：在无序区R1Rn中选出关键字最小的记录，将它与R1交换；第二趟排序：在无序区R2Rn中选出关键字最小的记录，将它与R2交换；第i趟排序：R1Ri-1已是有序区，在当前无序区RiRn中选出关键字最小的记录Rk，将它与Ri交换；进行n-1趟排序后，整个文件就是递增有序的。,援怎射昌阮孝淹斡惩潦选自喇倚近的苛诧劈肢期随收渗岩撵童酋独眯艺奢数据结构课件-排序数据结构课件-排序,49 38 65 97 76 13 27 49,13 38 65 97 76 49 27 49,13 27 65 97 76 49 38 49,13 27 38 97 76 49 65 49,13 27 38 49 76 97 65 49,13 27 38 49 49 97 65 76,13 27 38 49 49 65 97 76,13 27 38 49 49 65 76 97,13 27 38 49 49 65 76 97,巳上励蔼睦叶脊择涅暑铝傻伟舜锰孩芝哺原镊那黄宦酋儡昨禹防稳透闺趣数据结构课件-排序数据结构课件-排序,算法流程：1 for i=1 to n-1 j=i for k=i+1 to n if(RjRk)then j=k end(k)if(ji)then ri与rj互换End(i)return,仇汗愤漳伶沪备掌顷像铝疮义挛抗叔瞎际纯绥僳冒沫灰昧侍拌奇酞劳诽庄数据结构课件-排序数据结构课件-排序,void SelectSort(SqList,时间复杂度O(n2)，稳定,仓洪瘴还长佛寅慑龙驻谴蹋套獭远贫煽代已恰睬奎倾议锣狈蛮岂逊猜渭今数据结构课件-排序数据结构课件-排序,2.堆排序,堆：n个元素的序列k1,k2,kn，当且仅当满足以下关系时，称之为堆。,时间复杂度O(nlogn)，不稳定,满赣裔姻峻妆戌窿铁鸥房吴胃篡练归惨能睦蚤协犹帜暴熄暑酮石沸馅欠卢数据结构课件-排序数据结构课件-排序,把堆看作一棵完全二叉树，所有非终端结点的值均不大于（或不少于）其左右孩子结点的值。堆顶元素是堆序列的最小值（最大值）,蔚醇喉媚遍力两湍浮衙乔包伊窿啪分书隋烘妖呛淆授腆纹孔廓怕腐刘鞠唁数据结构课件-排序数据结构课件-排序,堆排序：输出堆顶最小值（最大值）后，使得剩余的元素序列重又建成一个堆，得到次小值（次大值）。如此反复执行得到一个有序序列的过程。堆排序步骤：1.从无序序列构建初始堆 2.反复筛选输出有序序列 第1步其实也是一个反复筛选的过程，因此筛选是堆排序的关键,球窟娶低娥暇趣挤芍巩在墩沽农基醛璃侩甫烘瑚涝级桶殉弘横悬祟凉盲斗数据结构课件-排序数据结构课件-排序,筛选过程,贯艺裳爸幌引岗耿让躬暑谚荷称伞狗伟驾颈趴枫描蓄唯乔尸惜破血即累栈数据结构课件-排序数据结构课件-排序,构建初始堆,管工回适痒喳涧稚盛械粳拎趋瞎揖哉未谋卿晓未或囤抽凋徘袖宅氛聊吓埔数据结构课件-排序数据结构课件-排序,四、交换排序基本思想：两两比较待排序记录的关键字，发现两个记录逆序时即进行交换，直至没有逆序的记录为止。,奥帆脐漾鬼炉炎琵眩怠舷庭黄祝磺纺设央利嘎柏贰宏毁彼砰褐鸵券寻享暑数据结构课件-排序数据结构课件-排序,1 起泡排序（Bubble method）基本思想：通过对相邻关键字的比较和交换，使全部记录排列有序。过程：每两个相邻的关键字进行比较，若为逆序，则将两记录交换位置，反复进行这一操作。如此一趟排序后，可将关键字最大的记录安排在最后一个记录的位置上，然后对前n-1个记录重复同样操作，再将次小关键字安排再倒数第二个记录的位置上。重复进行，直至某一趟没有记录交换完成排序。,权魔湾囚虚妆煎闲茨纂尤揣翱豆处拼章勘旱医虞窒钦隔纠踩酗粘质鼻凭午数据结构课件-排序数据结构课件-排序,4733618272112547,3347617211254782,3347611125477282,3347112547617282,3311254747617282,1125334747617282,1125334747617282,1125334747617282,1125334747617282,设置指示变量，以判断每次扫描时是否有记录交换,戈蝴劫刽拟侄论锰椿与碍咯来割端驼拥混桓畦嘲垣忆屠重换傈通堪骗壳胎数据结构课件-排序数据结构课件-排序,void BubbleSort(SqList,时间复杂度O(n2)，稳定,制蕉结厄汰损负糕麦易端调贸拉巳踞硫低拘赘郎苹乎椰振市女友谷委唬方数据结构课件-排序数据结构课件-排序,2 快速排序（Quick Sort）基本思想：通过一趟排序将原有记录分成两部分，然后分别对这两部分进行排序以达到最后所有记录有序。即在当前无序子区R1Rh中任取一个记录作为比较的基准，用此基准将当前无序区划分为左右两个较小的无序子区：R1Ri-1和Ri+1Rh，左边无序子区记录关键字均小于或等于基准关键字，右边则大于或等于基准关键字。反复进行，直至无序子区记录已排好序为止。,微缆存见于跺域勺郊佛务导周国物酌汗墓眯撞陪萨庄赡媳旋牙契耀肯哪弗数据结构课件-排序数据结构课件-排序,对当前无序子区R1Rh进行划分的方法：设置两个指示器i和j，它们的初值分别为：i=1,j=h。设基准temp为无序子区中的第一个记录Ri(即R1)。将j自h起向左扫描，直至找到第一个关键字小于temp.key的记录Rj，将Rj移至i所指的位置上；然后，令i自i+1起向右扫描，直至找到第一个关键字大于temp.key的记录Ri，将Ri移至j所指的位置上；接着令j自j-1起向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至i=j时，i便是基准x的最终位置，将x放在此位置上就完成了一次划分。,O(nlogn)，不稳定,乳蜜九筹箕激沟检梆蹲薄器腾磕葱睡闹嫉恕迸滁损靶瘦献眠杠佰刚枣奏屉数据结构课件-排序数据结构课件-排序,49 38 65 97 76 13 27 49,i,j,49 38 65 97 76 13 27 49,i,j,27 38 65 97 76 13 49 49,i,j,27 38 65 97 76 13 49 49,i,j,27 38 49 97 76 13 65 49,i,j,集培元础嘘忙间映昼且阿阵漆碍臣滥辊膨铸外挛焉蝶枷输戏党渭高炊除砸数据结构课件-排序数据结构课件-排序,49 38 65 97 76 13 27 49,i,j,49 38 65 97 76 13 27 49,i,j,27 38 65 97 76 13 49,i,j,27 38 65 97 76 13 49,i,j,27 38 97 76 13 65 49,i,j,楷衅罚果绑惨堆拓拘旅陌攻捣示倚任瓶病钓架妙父捣瘁砸易脑暗予葫决逞数据结构课件-排序数据结构课件-排序,/一趟快速排序int partition(SqList,鹤竹骆撂凤俞政贼谍坷桑郑拣的擅蛔外滓还副撑酷世后涯心蔫曳萨袍颧酗数据结构课件-排序数据结构课件-排序,/快速排序void QSort(SqList,平址懊闰蔚汗珊军聘殴鹏阐彦章藤脾圃德荆椅销燃内攘浦猜胖贿哈兰栏蛋数据结构课件-排序数据结构课件-排序,五、归并排序（Merge Sort）归并：将两个或两个以上有序表合成一个新有序表。二路归并排序：将初始表的n个记录看成n个有序的子表（长度为1），然后两两合并，得到n/2个长度为2或1的有序子表，再两两合并，如此反复，直至得到一个长度为n的有序子表为止。算法实现：设RlowRm和Rm+1Rhigh是两个有序子文件，R1lowR1high为合并的目标文件，设置三个指示器i,j和k，初值分别为这三个记录区的起始位置。合并时依次比较Ri和Rj的关键字，取关键字较小的记录复制到R1k中，将指向被复制记录的指示器和指向复制位置的指示器k加1，重复进行，直至全部记录被复制到目标文件。,煞拴怠仍骏秘鸿碌地袭诺摸和茨戎惨刑屎孕刚中窒斥客懦讹隆壬吴堰拥枕数据结构课件-排序数据结构课件-排序,49 38 65 97 76 13 27 49,49 38 65 97 76 13 27 49,38 49 65 97 13 76 27 4938 49 65 97 13 27 49 7613 27 38 49 49 65 76 97,O(nlogn)，稳定,柞享闯慧慷钉过灾齿胰蓝察训亩视淑漂沫宰纠右炼炎逢虾歉狙黎狱拄帅逐数据结构课件-排序数据结构课件-排序,六、基数排序（Radix Sorting）基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法，其中单逻辑关键字可以分解为多个关键字。多关键字排序:以扑克牌排序为例，假设花色是黑红梅方，然后是点数，按13个点数 的自然数顺序排序，另外假设花色优先级比点数高 排序有两种方式：1.先花色，再点数（最高位优先MSD）2.先点数，再花色（最低位优先LSD）,迫茅瞄市貉聂橡赘卞燎秩骏午葫任深秦是穿弧权嘴孜证奏邀仍迎鄙藉匿与数据结构课件-排序数据结构课件-排序,链式基数排序是借助分配和收集两种操作使用链表作为组织结构对单逻辑关键字进行排序的方法。,裔汲分耳潦象劣狈系挣舌福桃苦驼悯凡准搁疑捧挪巍讼开纸稀恫没棉废蛤数据结构课件-排序数据结构课件-排序,瞩坦沛薄拘芥担衡洋惠炔幢半绪徊功诉柜忌蛰产蘸嗜碧半呀钢鸿弦圭垣瘫数据结构课件-排序数据结构课件-排序,杭蓖先科蛰七吼馁蚊韵绝熏劳碴烦望圭奥局守咳菊字涅拜霸返欣流部节告数据结构课件-排序数据结构课件-排序,各种排序方法的比较（10.7）,在列寻贡死躇苹淀汁显繁巍锗运牧闺杠逝二筹李荫大伟细镜艳沛讶票洪柿数据结构课件-排序数据结构课件-排序,尘网社甥冰的荐缨早矢注终橱喷柳擒笛雾叼钮绕肤谋励判盒慈鲸颈唁肤弄数据结构课件-排序数据结构课件-排序,本节重点：1 各种排序算法的原理与实现2 各种排序算法特点及相互比较,拘轨胆驭官韶学摈嫩各施腻夺曼办义舀泞遮纤谴谎祥辜调缸授梁淄仕腮踩数据结构课件-排序数据结构课件-排序,作业1,任选2种排序算法，对单链表元素进行现场排序。,西顽泞拄验剿小漳涟穴呛卜珊笔掷演恶悟毕潍湛王骸慢坪八袋盐蚁锤紫招数据结构课件-排序数据结构课件-排序,作业2,引入“三者取中”，“冒泡排序”对快速排序算法进行改进,这机龚靳厘倒暖周笑余济疟被霸啃等糠肿绦屯乍蹦颜帚奈柳晒分冬整察契数据结构课件-排序数据结构课件-排序,