数据结构与算法内部排序分析学习教案.pptx

会计学1数据结构数据结构(sh j ji u)与算法内部排序与算法内部排序分析分析第一页，共70页。10101 1概述概述(i sh)(i sh)一、排序的定义一、排序的定义一、排序的定义一、排序的定义 假设有假设有假设有假设有n n个记录的序列为：个记录的序列为：个记录的序列为：个记录的序列为：R1R1，R2R2，,Rn,Rn 其对应的关键字为其对应的关键字为其对应的关键字为其对应的关键字为K1K1，K2K2，,Kn,Kn 需要确定需要确定需要确定需要确定1 1，2 2，,n,n的一种排列的一种排列的一种排列的一种排列P1P1，P2P2，,Pn,Pn 使：使：使：使：Kp1Kp1K p2K p2K p nK p n 则则则则R p1R p1，R p2R p2，,R pn,R pn为一个为一个为一个为一个(y)(y)按关键字有序的序按关键字有序的序按关键字有序的序按关键字有序的序列。其中，列。其中，列。其中，列。其中，KiKi可以是记录可以是记录可以是记录可以是记录RiRi的主关键字、次关键字或若干数据项的主关键字、次关键字或若干数据项的主关键字、次关键字或若干数据项的主关键字、次关键字或若干数据项的组合。的组合。的组合。的组合。第1页/共70页第二页，共70页。二、排序方法的稳定二、排序方法的稳定二、排序方法的稳定二、排序方法的稳定(wndng)(wndng)(wndng)(wndng)性性性性 若若若若Ki=Kj,(1Ki=Kj,(1Ki=Kj,(1Ki=Kj,(1 i i i i j j j j n),n),n),n),且排序前，且排序前，且排序前，且排序前，RiRiRiRi在在在在RjRjRjRj前面，前面，前面，前面，若排序后，若排序后，若排序后，若排序后，RiRiRiRi仍在仍在仍在仍在RjRjRjRj前面前面前面前面 则则则则 称称称称 该该该该 排排排排 序序序序 算算算算 法法法法 是是是是 稳稳稳稳 定定定定(wndng)(wndng)(wndng)(wndng)的的的的，否否否否 则则则则 是是是是 不不不不 稳稳稳稳 定定定定(wndng)(wndng)(wndng)(wndng)的。的。的。的。三、排序分类三、排序分类三、排序分类三、排序分类根据根据根据根据(gnj)(gnj)(gnj)(gnj)待排序的记录的数量划分：待排序的记录的数量划分：待排序的记录的数量划分：待排序的记录的数量划分：内部排序：内部排序：内部排序：内部排序：待排序的记录存放在计算机的内存中的排序过程待排序的记录存放在计算机的内存中的排序过程待排序的记录存放在计算机的内存中的排序过程待排序的记录存放在计算机的内存中的排序过程外部排序：外部排序：外部排序：外部排序：待待待待排排排排序序序序的的的的记记记记录录录录数数数数量量量量很很很很大大大大，内内内内存存存存一一一一次次次次放放放放不不不不下下下下全全全全部部部部记记记记录录录录，在在在在排排排排序序序序过程中还需访问外存的排序过程。过程中还需访问外存的排序过程。过程中还需访问外存的排序过程。过程中还需访问外存的排序过程。第2页/共70页第三页，共70页。四四四四、内内内内部部部部排排排排序序序序(pi(pi(pi(pi x)x)x)x)方法方法方法方法 插入排序插入排序插入排序插入排序(pi x)(pi x)(pi x)(pi x)交换排序交换排序交换排序交换排序(pi x)(pi x)(pi x)(pi x)选择排序选择排序选择排序选择排序(pi x)(pi x)(pi x)(pi x)归并排序归并排序归并排序归并排序(pi x)(pi x)(pi x)(pi x)基数排序基数排序基数排序基数排序(pi x)(pi x)(pi x)(pi x)五、待排序记录的存储五、待排序记录的存储五、待排序记录的存储五、待排序记录的存储(cn ch)(cn ch)(cn ch)(cn ch)方式方式方式方式 存放在地址连续的一组存储存放在地址连续的一组存储存放在地址连续的一组存储存放在地址连续的一组存储(cn ch)(cn ch)(cn ch)(cn ch)单元单元单元单元-约定约定约定约定 存放在静态链表存放在静态链表存放在静态链表存放在静态链表 存放在地址连续的一组存储存放在地址连续的一组存储存放在地址连续的一组存储存放在地址连续的一组存储(cn ch)(cn ch)(cn ch)(cn ch)单元，另设一组索引指针单元，另设一组索引指针单元，另设一组索引指针单元，另设一组索引指针第3页/共70页第四页，共70页。#define MAXSIZE 20#define MAXSIZE 20 /一一一一个个个个用用用用作作作作示示示示例例例例的的的的小小小小顺顺顺顺序序序序表表表表的的的的最最最最大长度大长度大长度大长度(chngd)(chngd)typedef int KeyType;/typedef int KeyType;/定义关键字类型为整数类型定义关键字类型为整数类型定义关键字类型为整数类型定义关键字类型为整数类型typedef structtypedef struct KeyType key;KeyType key;/关键字关键字关键字关键字 InfoType otherinfo;InfoType otherinfo;/其它数据项其它数据项其它数据项其它数据项RedType;RedType;/记录类型记录类型记录类型记录类型typedef structtypedef struct RedType rMAXSIZE;RedType rMAXSIZE;/r0 /r0赋闲或用作哨兵单元赋闲或用作哨兵单元赋闲或用作哨兵单元赋闲或用作哨兵单元 int length;int length;/顺序表长度顺序表长度顺序表长度顺序表长度(chngd)(chngd)SqList;SqList;第4页/共70页第五页，共70页。10102 2插入排序插入排序insert sortinginsert sorting一、直接插入排序一、直接插入排序一、直接插入排序一、直接插入排序 方法：将一个方法：将一个方法：将一个方法：将一个(y)(y)(y)(y)记录插入已排好序的有序表中，得到记录插入已排好序的有序表中，得到记录插入已排好序的有序表中，得到记录插入已排好序的有序表中，得到一个一个一个一个(y)(y)(y)(y)新的记录数增加新的记录数增加新的记录数增加新的记录数增加1 1 1 1的有序表的有序表的有序表的有序表（1 1 1 1）把序列）把序列）把序列）把序列(R(K1)(R(K1)(R(K1)(R(K1)看成是一个看成是一个看成是一个看成是一个(y)(y)(y)(y)有序的子序列有序的子序列有序的子序列有序的子序列 把把把把R(K2)R(K2)R(K2)R(K2)插入到该序列中插入到该序列中插入到该序列中插入到该序列中,使插入后序列使插入后序列使插入后序列使插入后序列 (R(K1),R(K2)(R(K1),R(K2)(R(K1),R(K2)(R(K1),R(K2)有序有序有序有序（2 2 2 2）把）把）把）把R(K3)R(K3)R(K3)R(K3)插入到插入到插入到插入到(R(K1),R(K2)(R(K1),R(K2)(R(K1),R(K2)(R(K1),R(K2)中，中，中，中，使插入后有序使插入后有序使插入后有序使插入后有序（3 3 3 3）重复（）重复（）重复（）重复（2 2 2 2），直到插入），直到插入），直到插入），直到插入R(Kn)R(Kn)R(Kn)R(Kn)为止。为止。为止。为止。第5页/共70页第六页，共70页。7目录页张铭、邹艳珍、刘楚雄、闫宏飞、郝丹数据结构与算法插入排序动画 1234322964453478第6页/共70页第七页，共70页。45，34，78，12，34，32，29，64 45 45 34 45 34 45 34 45 78 34 45 78 12 34 45 78 12 34 45 78 12 34 12 34 3434 45 78 45 78 12 32 34 12 32 34 3434 45 78 45 78 12 29 32 34 12 29 32 34 3434 45 78 45 78 12 29 32 34 34 45 64 78 12 29 32 34 34 45 64 78第7页/共70页第八页，共70页。void InsertSort(SqList&L)void InsertSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L做直接插入做直接插入做直接插入做直接插入(ch r)(ch r)排序排序排序排序 for(i=2;i=L.length;+i)for(i=2;i=L.length;+i)if(LT(L.ri.key,L.ri-1.key)if(LT(L.ri.key,L.ri-1.key)/将将将将L.riL.ri插插插插入入入入(ch(ch r)r)有有有有序序序序子子子子表表表表 L.r0=L.ri;L.r0=L.ri;for(j=i-1;LT(L.r0.key,L.rj.key);-j)for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.rj;/记录后移记录后移记录后移记录后移 L.rj+1=L.r0;L.rj+1=L.r0;/插入插入插入插入(ch r)(ch r)到正确位置到正确位置到正确位置到正确位置 /InsertSort/InsertSort第8页/共70页第九页，共70页。算法算法(sun f)分析分析稳定空间代价：O(n)时间(shjin)代价：最佳情况：n-1次比较，O(n)最差情况：O(n2)比较次数为平均情况：O(n2)第9页/共70页第十页，共70页。例：在序列例：在序列例：在序列例：在序列(xli)13(xli)13(xli)13(xli)13，27272727，35353535，48484848，65656565，72727272中插入中插入中插入中插入20202020或或或或606060603565132748722060二、折半插入排序二、折半插入排序二、折半插入排序二、折半插入排序Binary Insertsort Binary Insertsort Binary Insertsort Binary Insertsort 用折半查找的方法用折半查找的方法用折半查找的方法用折半查找的方法(fngf)(fngf)(fngf)(fngf)找到插入位置找到插入位置找到插入位置找到插入位置第10页/共70页第十一页，共70页。void BInsertSort(SqList&L)void BInsertSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L做折半做折半做折半做折半(zhbn)(zhbn)插入排序插入排序插入排序插入排序 for(i=2;i=L.length;+i)for(i=2;i=L.length;+i)L.r0=L.ri;L.r0=L.ri;/将将将将L.riL.ri暂存到暂存到暂存到暂存到L.r0L.r0 low=1;hight=i-1;low=1;hight=i-1;while(low=hight)while(low=hight+1;-j)L.rj+1=L.rj;/for(j=i-1;j=hight+1;-j)L.rj+1=L.rj;/记录后移记录后移记录后移记录后移 L.rhight+1=L.r0;L.rhight+1=L.r0;/插入到正确位置插入到正确位置插入到正确位置插入到正确位置 /BInsertSort/BInsertSort第11页/共70页第十二页，共70页。四四、希希尔尔排排序序(pi(pi x)x)（缩缩小小增增量量排排序序(pi x)Shell Sort(pi x)Shell Sort）思想：先将序列转化为若干小序列，在这些小序列内进行插入排序逐渐增加小序列的规模，而减少小序列个数，使得待排序序列逐渐处于(chy)更有序的状态最后对整个序列进行一趟直接插入排序直接插入排序的两个特点：在最好情况下时间代价为O(n)对于(duy)短序列，直接插入排序比较有效第14页/共70页第十五页，共70页。按增量序列将整个待排记录分割成若干个序列，分别进行直接插入排序。等整个序列基本有序后，再对全体记录进行一次直接插入排序。按增量序列将整个待排记录分割成若干个序列，分别进行直接插入排序。等整个序列基本有序后，再对全体记录进行一次直接插入排序。基本有序：序列中满足基本有序：序列中满足(mnz)(mnz)以下特性的记录较少以下特性的记录较少方法方法(fngf)(fngf)：第15页/共70页第十六页，共70页。17目录页张铭、邹艳珍、刘楚雄、闫宏飞、郝丹数据结构与算法Shell排序(pi x)动画 12343229644534781234322964453478123432296445347812343229644534781234322964453478第16页/共70页第十七页，共70页。增量增量(zn lin)(zn lin)序列为：序列为：5 5，3 3，1 14949 3838 6565 9797 76 76 1313 2727 49491313 2727 4949 9797 76 76 4949 38 38 65651313 2727 4949 9797 7676 4949 3838 65 651313 2727 4949 3838 6565 4949 9797 76 7613 27 38 13 27 38 4949 49 65 76 97 49 65 76 97第17页/共70页第十八页，共70页。void ShellInsert(SqList&L,int dk)void ShellInsert(SqList&L,int dk)/对顺序表对顺序表对顺序表对顺序表L L作一趟希尔插入排序作一趟希尔插入排序作一趟希尔插入排序作一趟希尔插入排序./本算法与一趟直接插入排序比较本算法与一趟直接插入排序比较本算法与一趟直接插入排序比较本算法与一趟直接插入排序比较(bjio),(bjio),作了以下修改作了以下修改作了以下修改作了以下修改 /1./1.前后记录位置的增量是前后记录位置的增量是前后记录位置的增量是前后记录位置的增量是dk,dk,而不是而不是而不是而不是1 1 /2.r0/2.r0只只只只是是是是暂暂暂暂存存存存单单单单元元元元，不不不不是是是是哨哨哨哨兵兵兵兵。当当当当j=0j=0时时时时，插插插插入入入入位位位位置置置置已已已已找到找到找到找到 for(i=dk+1;i=L.length;+i)for(i=dk+1;i0&LT(L.r0.kry,L.rj.key);j-=dk)for(j=i-dk;j0&LT(L.r0.kry,L.rj.key);j-=dk)L.rj+dk=L.rj;L.rj+dk=L.rj;/记记记记录录录录后后后后移移移移，查查查查找找找找插插插插入入入入位位位位置置置置 L.rj+dk=L.r0;L.rj+dk=L.r0;/插入插入插入插入 /ShellInsert/ShellInsert第18页/共70页第十九页，共70页。void ShellSort(SqList&L,int dlta,int t)/按按增增量量序序列列dlta0.t-1对对顺顺序序(shnx)表表L作作希希尔尔排序排序 for(k=0;kt;+t)ShellInsert(L,dltak);/一一趟趟增增量量为为daltk的的插插入入排序排序/ShellSort第19页/共70页第二十页，共70页。不稳定空间代价：O(n)时间代价增量序列不合适时，O(n2)选择适当的增量序列,可以使得(shde)时间代价接近O(n)Hibbard增量序列2k-1，2k-1-1，7，3，1Hibbard增量序列的Shell排序的效率可以达到O(n3/2)呈2p3q形式的一系列整数：1,2,3,4,6,8,9,12时间代价为O(nlog2n)算法算法(sun f)分析分析第20页/共70页第二十一页，共70页。10103 3快速排序快速排序(pi x)(pi x)一、起泡排序一、起泡排序(pi x)Bubble Sort(pi x)Bubble Sort算法思想:依次比较相邻的记录(jl)，如果不满足排序要求，就交换相邻记录(jl)，直到所有的记录(jl)都已经排好序检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束，避免不必要的比较第21页/共70页第二十二页，共70页。void BubbleSort(SqList&L)for(i=1;iL.length;i+)change=FALSE;for(j=1;jL.rj+1.key)change=TRUE;L.rjL.rj+1;if(!change)return;共共 进进 行行(jnxng)n-1(jnxng)n-1趟趟排序，排序，共共 进进 行行(jnxng)n(n-(jnxng)n(n-1)/21)/2次比较次比较T(n)=O(n2)T(n)=O(n2)第22页/共70页第二十三页，共70页。算法算法(sun f)分析分析稳定空间(kngjin)代价：O(n)时间代价：比较次数最少：O(n)最多：交换(jiohun)次数最多为O(n2)，最少为0，平均为O(n2)最坏，平均时间代价均为O(n2)最好时间代价为O(n)第23页/共70页第二十四页，共70页。二、快速二、快速二、快速二、快速(kui s)(kui s)排序排序排序排序Quick SortQuick Sort基本思想：基本思想：通过一趟排序将待排序记录分成独立的两部分，通过一趟排序将待排序记录分成独立的两部分，其中一部分记录的关键字均小于另一部分记录其中一部分记录的关键字均小于另一部分记录 的关键字，然后的关键字，然后(rnhu)分别对这两部分进行递归排序分别对这两部分进行递归排序 一趟排序：一趟排序：一趟排序：一趟排序：任意选取一个记录作为枢轴（支点）任意选取一个记录作为枢轴（支点）任意选取一个记录作为枢轴（支点）任意选取一个记录作为枢轴（支点）pivot,pivot,将所有关将所有关将所有关将所有关键字小于它的记录排在它的前面键字小于它的记录排在它的前面键字小于它的记录排在它的前面键字小于它的记录排在它的前面,将所有关键字大于将所有关键字大于将所有关键字大于将所有关键字大于它的记录排在它的后面。即以枢轴记录为分界线，使原它的记录排在它的后面。即以枢轴记录为分界线，使原它的记录排在它的后面。即以枢轴记录为分界线，使原它的记录排在它的后面。即以枢轴记录为分界线，使原序列序列序列序列L.rs,L.rs+1,L.rtL.rs,L.rs+1,L.rt分成分成分成分成(fn chn)(fn chn)两个子两个子两个子两个子序列：序列：序列：序列：L.rs,L.rs+1,L.ri-1 L.rs,L.rs+1,L.ri-1和和和和 L.ri+1,L.ri+2,L.rt L.ri+1,L.ri+2,L.rt 枢轴记录在位置枢轴记录在位置枢轴记录在位置枢轴记录在位置i i第24页/共70页第二十五页，共70页。49 38 65 97 76 13 27 49i27 38 65 97 76 13 49 4927 38 49 97 76 13 65 49jiiijjijj27 38 13 97 76 49 65 49iji27 38 13 49 76 97 65 49ij27 38 1376 97 65 76 97 65 4949jj第25页/共70页第二十六页，共70页。具体实现：具体实现：具体实现：具体实现：low=s;high=t;pivotkey=L.rlow.key;low=s;high=t;pivotkey=L.rlow.key;(1)(1)从从从从highhigh开开开开始始始始往往往往前前前前找找找找第第第第一一一一个个个个关关关关键键键键字字字字小小小小于于于于pivotkeypivotkey的的的的记记记记录录录录(jl)(jl)，与枢轴记录，与枢轴记录，与枢轴记录，与枢轴记录(jl)(jl)交换交换交换交换 (2)(2)从从从从lowlow开开开开始始始始往往往往后后后后找找找找第第第第一一一一个个个个关关关关键键键键字字字字大大大大于于于于pivotkeypivotkey的的的的记记记记录录录录(jl)(jl)，与枢轴记录，与枢轴记录，与枢轴记录，与枢轴记录(jl)(jl)交换交换交换交换(3)(3)重复（重复（重复（重复（1 1）（）（）（）（2 2）直到）直到）直到）直到low=highlow=high为止为止为止为止此时枢轴记录此时枢轴记录此时枢轴记录此时枢轴记录(jl)(jl)所在的位置所在的位置所在的位置所在的位置i=low=highi=low=high27 38 13 49 76 97 65 491313 2727 38384949 65 65 7676 97 97 第26页/共70页第二十七页，共70页。int partition(SqList&L,int low,int high)int partition(SqList&L,int low,int high)/交交交交换换换换顺顺顺顺序序序序表表表表L L中中中中的的的的子子子子表表表表L.rlow.highL.rlow.high的的的的记记记记录录录录,枢枢枢枢轴轴轴轴记记记记录录录录到到到到位位位位,并返回其所在位置并返回其所在位置并返回其所在位置并返回其所在位置/此时在它之前（后）的记录均不大（小）于它此时在它之前（后）的记录均不大（小）于它此时在它之前（后）的记录均不大（小）于它此时在它之前（后）的记录均不大（小）于它 piovtkey=L.rlow.key;piovtkey=L.rlow.key;/用用用用子子子子表表表表的的的的第第第第一一一一个个个个记记记记录录录录作作作作枢枢枢枢轴轴轴轴记记记记录录录录 while(lowhigh)while(lowhigh)/从从从从 表表表表 的的的的 两两两两 端端端端 交交交交 替替替替 地地地地 向向向向 中中中中 间间间间(zhngjin)(zhngjin)扫描扫描扫描扫描 while(low=priotkey)while(low=priotkey)-high;-high;L.rlow L.rlow L.rhigh;L.rhigh;/将比枢轴记录小的记录交换到低端将比枢轴记录小的记录交换到低端将比枢轴记录小的记录交换到低端将比枢轴记录小的记录交换到低端 while(lowhigh&L.rlow.key=priotkey)while(lowhigh&L.rlow.key=priotkey)+low;+low;L.rlow L.rlow L.rhigh;L.rhigh;/将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端将比枢轴记录大的记录交换到高端 return low;return low;/返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置/Partition/Partition第27页/共70页第二十八页，共70页。int partition(SqList&L,int low,int high)int partition(SqList&L,int low,int high)/交交交交换换换换顺顺顺顺序序序序表表表表L L中中中中的的的的子子子子表表表表L.rlow.highL.rlow.high的的的的记记记记录录录录，枢枢枢枢轴轴轴轴记记记记录录录录到到到到位位位位(do wi)(do wi)，/并并并并返返返返回回回回其其其其所所所所在在在在位位位位置置置置。此此此此时时时时在在在在它它它它之之之之前前前前（后后后后）的的的的记记记记录录录录均均均均不不不不大大大大（小小小小）于它于它于它于它 L.r0=L.rlow;L.r0=L.rlow;/用用用用子子子子表表表表的的的的第第第第一一一一个个个个记记记记录录录录作作作作枢枢枢枢轴轴轴轴记录记录记录记录 pivotkey=L.rlow.key;pivotkey=L.rlow.key;/枢轴记录关键字枢轴记录关键字枢轴记录关键字枢轴记录关键字 while(lowhigh)while(lowhigh)/从表的两端交替地向中间扫描从表的两端交替地向中间扫描从表的两端交替地向中间扫描从表的两端交替地向中间扫描 while(low=pivotkey)while(low=pivotkey)-high;-high;L.rlow=L.rhigh;L.rlow=L.rhigh;/将将将将比比比比枢枢枢枢轴轴轴轴记记记记录录录录小小小小的的的的记记记记录录录录交交交交换换换换到到到到低端低端低端低端 while(lowhigh&L.rlow.key=pivotkey)+low;while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rhigh=L.rlow;/将将将将比比比比枢枢枢枢轴轴轴轴记记记记录录录录大大大大的的的的记记记记录录录录交交交交换换换换到到到到高端高端高端高端 L.rlow=L.r0;L.rlow=L.r0;/枢轴记录到位枢轴记录到位枢轴记录到位枢轴记录到位(do wi)(do wi)return low;return low;/返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置返回枢轴所在的位置/Partition/Partition第28页/共70页第二十九页，共70页。void Qsort(SqList&L,int low,int high)void Qsort(SqList&L,int low,int high)/对顺序表对顺序表对顺序表对顺序表L L中的子表中的子表中的子表中的子表L.rlow.highL.rlow.high作快速排序作快速排序作快速排序作快速排序 if(lowhigh)/if(lowhigh)/长度大于长度大于长度大于长度大于1 1 pivotloc=partition(L,low,high);pivotloc=partition(L,low,high);/将将将将L.rlow.highL.rlow.high一分为二一分为二一分为二一分为二 Qsort(L,low,pivotloc-1);Qsort(L,low,pivotloc-1);/对低子表递归排序，对低子表递归排序，对低子表递归排序，对低子表递归排序，pivotlocpivotloc是枢轴是枢轴是枢轴是枢轴(sh zhu)(sh zhu)位置位置位置位置 Qsort(L,pivotloc+1,high);Qsort(L,pivotloc+1,high);/对高子表递归排序对高子表递归排序对高子表递归排序对高子表递归排序 /Qsort/Qsortvoid QuickSort(SqList&L)void QuickSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L作快速作快速作快速作快速(kui s)(kui s)排序排序排序排序 QSort(L,1,L.length);QSort(L,1,L.length);/QuickSort/QuickSort第29页/共70页第三十页，共70页。枢轴记录枢轴记录(jl)的选择的选择尽可能使两部分长度相等选择策略(cl)：选择最左/右/中间位置记录随机选择选择平均值第30页/共70页第三十一页，共70页。算法算法(sun f)分析分析最差情况：时间代价：O(n2)空间(kngjin)代价：O(n)最佳情况：时间代价：O(nlogn)空间(kngjin)代价：O(logn)平均情况：时间代价：O(nlogn)空间(kngjin)代价：O(logn)第31页/共70页第三十二页，共70页。T(n)=O(nlog2n)第32页/共70页第三十三页，共70页。34目录页张铭、邹艳珍、刘楚雄、闫宏飞、郝丹数据结构与算法1234322964453478101010104 4 4 4选择排序选择排序选择排序选择排序(pi x)(pi x)(pi x)(pi x)一、简单选择排序一、简单选择排序一、简单选择排序一、简单选择排序(pi x)Select Sort(pi x)Select Sort(pi x)Select Sort(pi x)Select Sort第33页/共70页第三十四页，共70页。void SelectSort(SqList&L)void SelectSort(SqList&L)/对顺序表对顺序表对顺序表对顺序表L L作简单选择作简单选择作简单选择作简单选择(xunz)(xunz)排序排序排序排序 for(i=1;iL.length;for(i=1;iL.length;+i)+i)/选选选选择择择择(xunz)(xunz)第第第第i i个个个个最最最最小小小小的的的的记记记记录录录录，并交换到位并交换到位并交换到位并交换到位 j=SelectMinkey(L,i);j=SelectMinkey(L,i);/在在在在 L.ri.L.lengthL.ri.L.length中中中中 选选选选 择择择择(xunz)key(xunz)key最小的记录最小的记录最小的记录最小的记录 if(i!=j)L.rj if(i!=j)L.rj L.ri;/L.ri;/与第与第与第与第i i记录交换记录交换记录交换记录交换 int SelectMinKey(SqList L,int k)int SelectMinKey(SqList L,int k)/在在在在L.rk.L.lengthL.rk.L.length中中中中选选选选择择择择(xunz)key(xunz)key最最最最小小小小的的的的记记记记录录录录并返回它的位置并返回它的位置并返回它的位置并返回它的位置 min=L.rk.key;minp=k;min=L.rk.key;minp=k;for(i=k+1;i=L.length;i+)for(i=k+1;i=L.length;i+)if(L.ri.keymin)if(L.ri.keymin)min=L.ri.key;minp=i;min=L.ri.key;minp=i;return minp;return minp;第34页/共70页第三十五页，共70页。不稳定空间代价：O(n)时间代价共进行n-1趟排序比较(bjio)次数：O(n2)交换次数：n-1总时间代价：O(n2)算法算法(sun f)分析分析第35页/共70页第三十六页，共70页。若若用用一一个个一一维维数数组组存存放放满满足足此此关关系系的的序序列列，把把这这个个一一维维数数组组看看成成是是一一棵棵完完全全二二叉叉树树，则则堆堆对对应应的的完完全全二二叉叉树树中中所所有有非非终终端端(zhn(zhn dun)dun)结结点点的的值均大于或均小于其左右孩子的值。值均大于或均小于其左右孩子的值。三、堆排序三、堆排序三、堆排序三、堆排序Heap SortHeap Sort堆的定义堆的定义堆的定义堆的定义：n n个元素的序列个元素的序列个元素的序列个元素的序列KK11，KK22，KKnn 当且仅当满足如下关系时称为当且仅当满足如下关系时称为当且仅当满足如下关系时称为当且仅当满足如下关系时称为堆堆堆堆：KKii KK2i2i 或或或或 KKii KK2i2i K Kii KK2i+12i+1 K Kii KK2i+12i+1第41页/共70页第四十二页，共70页。大大顶顶堆堆/大大根根堆堆堆排序方法：堆排序方法：（1 1）由一个无序的序列建成一个堆）由一个无序的序列建成一个堆（2 2）输出堆顶的最小值）输出堆顶的最小值（3 3）剩余的元素）剩余的元素(yun s)(yun s)建成一个新的堆建成一个新的堆（4 4）重复（）重复（2 2）（）（3 3）093811962783小小顶顶堆堆/小小根根堆堆3085471224369153第42页/共70页第四十三页，共70页。49 38 65 97 76 13 27 49输出输出1313后后,用序用序列中最后一个列中最后一个(y)(y)记录代记录代替根结点替根结点筛筛选选(shixun)为为堆堆顶顶元元素素与与它它的的左左右右子子树树根根(sh(sh n)n)结结点比较点比较若若右右子子树树根根(sh(sh n)n)左左子子树树根根(sh(sh n)n)堆顶堆顶 根结点与右子树根根结点与右子树根(sh n)(sh n)交换交换若若左左子子树树根根(sh(sh n)n)右右子子树树根根(sh(sh n)n)堆顶堆顶 根结点与左子树根根结点与左子树根(sh n)(sh n)交换交换这个调整过程称为筛选这个调整过程称为筛选13384976972765499738497627654927384976496597第43页/共70页第四十四页，共70页。对对一一个个无无序序序序列列建建立立(jinl)堆堆也也是是筛筛选选过过程程,筛筛选从选从n/2个记录开始。个记录开始。49 38 65 97 76 13 27 497627496538974913496538974997657649273813第44页/共70页第四十五页，共70页。499765764927381349386576492797134976654938279713第45页/共70页第四十六页，共70页。497665493827971349276549387697134965274938769713第46页/共70页第四十七页，共70页。496527493876971349132749387697651349274938769765第47页/共70页第四十八页，共70页。134927493876976549132749387697654949273813769765第48页/共70页第四十九页，共70页。494927381376976549132738497697654938271349769765第49页/共70页第五十页，共70页。494938382727131349497676979765654949272738381313494976769797656549491313383827274949767697976565建大顶堆，排序建大顶堆，排序(pi x)(pi x)结果为结果为从小到大从小到大第50页/共70页第五十一页，共70页。typedef SqList HeapType;typedef SqList HeapType;void HeapAdjust(HeapType&H,int s,int m)void HeapAdjust(HeapType&H,int s,int m)/已已已已知知知知H.rs.mH.rs.m中中中中记记记记录录录录的的的的关关关关键键键键字字字字除除除除H.rs.keyH.rs.key外外外外均均均均满满满满足足足足堆堆堆堆的的的的定定定定义，义，义，义，/本本本本函函函函数数数数调调调调整整整整H.rsH.rs的的的的关关关关键键键键字字字字，使使使使H.rs.mH.rs.m成成成成为为为为(chngwi)(chngwi)一一一一个大顶堆个大顶堆个大顶堆个大顶堆 rc=H.rs;rc=H.rs;for(j=2*s;j=m;j*=2)for(j=2*s;j=m;j*=2)/沿沿沿沿keykey较较较较大大大大的的的的孩孩孩孩子子子子结结结结点点点点向向向向下下下下筛筛筛筛选选选选 if(jm&LT(H.rj.key,H.rj+1.key)if(j0;-i)/for(i=H.length/2;i0;-i)/把把把把H.ri.lengthH.ri.length建成大建成大建成大建成大顶堆顶堆顶堆顶堆 HeapAdjust(H,i,H.leng