数据结构与算法分析??第七章 排序

发布时间:2021-09-18 14:56:10

7.1 预备知识


? ? ?1,算法接收 含元素的数组和包含元素个数的整数


? ? ?2,基于比较的排序


7.2 插入排序


? ? ?代码实现



void InsertionSort(ElementType A[],int N)
{
int i,j;
ElementType Tmp;
for(i = 1 ; i < N ; i++)
{
Tmp = A[i];
for(j = i ; j > 0 && A[j - 1] > Tmp ; j--)
{
A[j] = A[j - 1];
}
A[j] = Tmp;//避免明显使用交换
}
}

  理解描述


  位置i上元素存于Tmp中,i之前所有更大的元素向右移一位(i前所有元素已排序),Tmp被置于正确位置。


  分析


  1,(未排序)嵌套循环每个花费N次迭代,为O(N^2)


  2,(已排序)为O(N)



  *由于差距较大,故值得分析*均情形


?


7.3 一些简单排序算法的下界


  1,怎样概括“一些”的共性??  ? ??



? ? ? ?引入逆序 ?? 插排交换次数=逆序数(O(N) <=> O(N + I),N:其他工作,I:逆序数)?? *均运行时间 <=> *均逆序数


? ? ? ?* 以插排为例分析(插排 代表 通过交换相邻元素进行排序的算法),得出共性



  理解描述


  不断缩小增量的插入排序,通过远距离交换以达到一次消除多对逆序(需保证增量变换时不干扰已处理的顺序),减小每一趟工作量,即亚二次运行时间。


  分析


  定理7.3 ?使用希尔增量的希尔排序的最坏运行时间为Θ(N^2)


  定理7.4 ?使用 Hibbard 增量的希尔排序的最坏运行时间为Θ(N^2) ?(Hibbard增量形如 1,3,7,...,2^k - 1)


7.5 堆排序


  代码实现



#define LeftChild(i) (2 * (i) + 1)//下标从0开始,因此为 2*i+1
void PercDown(ElementType A[],int i,int N)
{
int Child;
ElementType Tmp;
for(Tmp = A[i] ; LeftChild(i) < N ; i = Child)//下标从0开始,注意边界
{
Child = LeftChild(i);
if(Child != N - 1 && A[Child + 1] > A[Child])//Child != N - 1 即右边还有数据
{
Child++;//选出较大的儿子
}
if(Tmp < A[Child])
{
A[i] = A[Child];
}
else
{
break;
}
}
A[i] = Tmp;
}
void HeapSort(ElementType A[] , int N)
{
int i;
//BuildHeap
for(i = N / 2 ; i >= 0 ; i--)//从右向左,从下向上,逐步下滤
{
PercDown(A,i,N);
}
//DeleteMax
for(i = N - 1 ; i > 0 ; i--)
{
Swap(&A[0] , &A[i]);
PercDown(A , 0 , i);//位置0处元素下滤,且元素个数改变

}
}


上图为构建初始堆及排序过程,数组中表,97.58,31,26,41,58,31  


  理解描述


  1,对已有数组元素进行整理,构建max堆(max堆便于实施从小到大排序)


  2,排序时通过回收利用空间,避免使用第二个数组


  分析


  定理7.5 ?对N个互异项的随机排列进行堆排序,所用的*均比较次数为 2NlogN - O(NlogN)


7.6归并排序


  代码实现



void MergeSort(ElementType A[],int N)//驱动例程
{
ElementType *TmpArray;
TmpArray = malloc(N * sizeof(ElementType));
if(TmpArray != NULL)
{
MSort(A,TmpArray,0,N - 1);
free(TmpArray);
}
else
{
FatalError("No space for tmp array");
}
}
void MSort(ElementType A[],ElementType TmpArray[],int Left,int Right)
{
int Center;
if(Left < Right)//条件成立时再对Center赋值
{
Center = (Left + Right) / 2;
MSort(A , TmpArray , Left , Center);
MSort(A , TmpArray , Center + 1 , Right);
Merge(A , TmpArray , Left , Center + 1 , Right);//Center + 1 即右半部分始位置
}
}
void Merge(ElementType A[] , ElementType TmpArray[] , int Lpos , int Rpos , int RightEnd)
{
int i , LeftEnd , TmpPos , NumElements;
//NumElements 存放每次排序时元素总数(临时数组元素转移至原数组时使用)
//TmpPos 记录排序元素在新建数组中*对应*位置

LeftEnd = Rpos - 1;
NumElements = RightEnd - Lpos;
TmpPos = Lpos;

while(Lpos < LeftEnd && Rpos < RightEnd)
{
if(A[Lpos] < A[Rpos])
{
TmpArray[TmpPos++] = A[Lpos++];
}
else
{
TmpArray[TmpPos++] = A[Rpos++];
}
}

//Copy rest of each half
while(Lpos <= LeftEnd)
{
TmpArray[TmpPos++] = A[Lpos++];
}
while(Rpos <= RightEnd)
{
TmpArray[TmpPos++] = A[Rpos++];
}

for(i = 0 ; i < NumElements ; i++ , RightEnd--)
{
A[RightEnd] = TmpArray[RightEnd];
}
}

  理解描述


  1,递归是怎样实施的?


  答:以8个元素为例,左右各分成4 个元素,先处理左边4 个,将左边4个元素重复分隔,直到左边只剩一个元素,达到基准条件,返回最*主程序中,处理右边一个元素,达到基准条件,进行合并,此时这两个元素作为左侧,返回最*主程序中,处理右边两个元素,继续先左后右,处理合并,返回最*主程序中,进行合并。此时总体来看,8个元素,左侧4个已实施“分治”,接下来继续进行递推,过程类似。


  2,小块元素合并后怎样存放?


  答:小块元素在临时数组*对应位置*进行合并存放,排序后依次放入原数组中,不影响后面元素及其排序。


  分析 


  运行时间:T(N) = O(NlogN)


  应用:很难用于主存排序。首先,合并两个线性表需要线性附加内存,其次,数据在数组间拷贝需要时间。 


7.7 快速排序


  代码实现



//驱动例程
void QuickSort(ElementType A[] , int N)
{
QSort(A , 0 , N - 1);
}

//选取枢纽元
//对三元素排序,最值放两边,枢纽元置于 right-1 处(此方法便于设置警戒标志,防止越界)
ElementType Median3(ElementType A[] , Left , Right)
{
int Center;
Center = (Left + Right) / 2;
if(A[Left] > A[Center])
{
Swap(&A[Left] , &A[Center]);
}
if(A[Left] > A[Right])
{
Swap(&A[Left] , &A[Right]);
}
if(A[Center] > A[Right])
{
Swap(&A[Center] , &A[Right]);
}
Swap(&A[Center] , &A[Right - 1]);
return A[Right - 1];
}

#define Cutoff (3)
void QSort(ElementType A[] , int Left , int Right)
{
int i , j;
ElementType Pivot;
if(Left + Cutoff <= Right)//数组内大于3个元素时,分割加递归
{
Pivot = Median3(A , Left , Right);
i = Left;//因为下方使用的是前自增
j = Right - 1;
for( ; ; )
{
while(A[++i] < Pivot){}
while(A[--j] > Pivot){}
if(i < j)
{
Swap(&A[i],&A[j]);
}
else
{
break;
}
}
Swap(&A[i],&A[Right - 1]);//Restore pivot
QSort(A , Left , i - 1);
QSort(A , i + 1 , Right);
}
else
{
InsertionSort(A + Left , Right - Left + 1);
}
}

  理解描述


  与归并排序类似,区别是选取枢纽元,以枢纽元为界分割为大小两数组。(适用于大数组)


  选取枢纽元:随机选取;三数中值分割法(左,右,中心位置里的中值,同时将三元素排序,便于设置警戒标志,防止越界)


  分割策略:1,枢纽元与位置right - 1处元素互换


       ? ?2,设置i(left),j(right - 1),i 向右滑动直至 i 处元素 >= 枢纽元,j 向左滑动直至 j 处元素 <= 枢纽元,交换i,j处元素


       ? ?3,i,j交错时,i 处元素与枢纽元交换


  分析


  最坏情况分析:枢纽元始终为最小元素,T(N) = O(N^2)


  最好情况分析:枢纽元位于中间,T(N) = O(NlogN)


  *均情况分析:每个文件大小等可能,求出*均分布,T(N) = O(NlogN)


  扩展(选择问题的线性期望时间算法)


  选择问题:查找集合S中第k个最小元


  与快速排序类似,区别在于分割后,若 k <= |S1|,则返回quickselect( S1 , k ),若k = |S1| + 1 ,则枢纽元即为所求,否则返回quickselect(S2 , k - |S1| - 1)


  代码实现



#define Cutoff (3)
void QuickSelect(ElementType A[] , int k , int N)
{
QSelect(A , k , 0 , N - 1);
}

ElementType Median3(ElementType A[] , Left , Right)
{
int Center;
Center = (Left + Right) / 2;
if(A[Left] > A[Center])
{
Swap(&A[Left] , &A[Center]);
}
if(A[Left] > A[Right])
{
Swap(&A[Left] , &A[Right]);
}
if(A[Center] > A[Right])
{
Swap(&A[Center] , &A[Right]);
}
Swap(&A[Center] , &A[Right - 1]);
return A[Right - 1];
}

//位置k - 1处即为第k个最小值
void QSelect(ElementType A[] , int k , int Left , int Right)
{
int i , j;
ElementType Pivot;
if(Left + Cutoff <= Right)
{
Pivot = Median3(A , Left , Right);
i = Left;
j = Right - 1;
for( ; ; )
{
while(A[++i] < Pivot){}
while(A[--j] > Pivot){}
if(i < j)
{
Swap(&A[i],&A[j]);
}
else
{
break;
}
}
Swap(&A[i],&A[Right - 1]);//Restore pivot
if(k <= i)
{
QSelect(A , k , Left , i - 1);
}
else if(k > i + 1)
{
QSelect(A , k - i - 1 , i + 1 , Right);
}
}
else
{
InsertionSort(A + Left , Right - Left + 1);
}
}

7.8 大型结构的排序


  排序时交换整个结构代价是昂贵的,解决办法是让输入数组包含指向结构的指针,通过指针比较关键字,必要时交换指针来进行排序。


7.9 排序的一般下界


  引入决策树,通过只使用比较进行排序的每一种算法都可以用决策树表示。


  引理7.1:令T是深度为d的二叉树,则T最多有2^d个树叶


  引理7.2:具有L片树叶的二叉树深度至少是[ logL ]


  定理7.6:只使用元素间比较的任何排序算法在最坏情况下至少需要[ log( N! ) ]次比较


  定理7.7:只使用元素间比较的任何排序算法需要进行Ω(NlogN)次比较


7.10 桶式排序


  以线性时间进行排序,构建数组,大小包含所有待排元素,初始为0,元素出现以1代替。


7.11 外部排序


  简单算法(该部分内容转自@Judy518)??二路合并


  例如要对外存中4500个记录进行归并,而内存大小只能容纳750个记录,在第一阶段,我们可以每次读取750个记录进行排序,这样可以分六次读取,进行排序,可以得到六 个有序的归并段,如下图:


  


每个归并段的大小是750个记录,记住,这些归并段已经全部写到临时缓冲区(由一个可用的磁盘充当)内了,这是第一步的排序结果。


1、将内存空间划分为三份,每份大小250个记录,其中两个用作输入缓冲区,另外一个用作输出缓冲区。首先对Segment_1和Segment_2进行归并,先从每个归并段中读取250个记录到输入缓冲区,对其归并,归并结果放到输出缓冲区,当输出缓冲区满后,将其写道临时缓冲区内,如果某个输入缓冲区空了,则从相应的归并段中再读取250个记录进行继续归并,反复以上步骤,直至Segment_1和Segment_2全都排好序,形成一个大小为1500的记录,然后对Segment_3和Segment_4、Segment_5和Segment_6进行同样的操作。


2、对归并好的大小为1500的记录进行如同步骤1一样的操作,进行继续排序,直至最后形成大小为4500的归并段,至此,排序结束。


  多路合并


  1,2-路合并扩充为k-路合并,区别在于寻找k个元素中最小元过程稍微复杂,可通过优先队列寻找最小元,进行DeleteMin操作,得到下一个写到磁盘上的元素


  2,在初始顺串构造阶段之后,k-路合并所需趟数为[ logk( N / M ) ]。(N为数据总量,M为内存容量)


  多相合并


  k-路合并需要2k盘磁带,然而使用 k + 1 盘磁带也有可能完成排序工作,作为例子,这里阐述只用三盘磁带(T1,T2,T3)如何完成2-路合并。


  假设T1上有一个输入文件,它将产生34个顺串。


  选择一:每盘磁带存入17个,然后合并存放至T1,再将T1前个8顺串存至T2,再次合并存至T3,依次类推。这样每一趟合并附加额外半趟工作。


  选择二:将34个顺串不均衡地分成2份,例如21,13,再次进行合并。此时需考虑顺串最初的分配,事实上,若初始顺串为斐波那契数,则将其分裂为2个斐波那契数之和,否则需添加哑顺串填补磁带,将其补足为斐波那契数


  替换选择(该部分内容转自@kph_Hajash)  


  在标准的外排中,一次读入内存可容纳的 M 个记录,排序完依次输出到空磁带上;但这里其实有个小技巧,排完序后输出第一个记录到磁带上时,内存让出了一个记录的空间,这时我们可以从输入磁带取出一个记录,判断它是否大于刚输出的记录,若是,说明它可以放入当前顺串中(顺串是从小到大有序),否则,应暂存内存,等下一个顺串的构造;?这里暂存内存书上讲是放在最小堆的死区(dead space)。


初始顺串的构造详解,绿色箭头表示当前输入状态,Tbn 表示输出状态,内存缓冲表示当前内存中存在的记录(括号内记录表示存在最小堆的死区)?

  


?




转载于:https://www.cnblogs.com/1025xrh/p/9557238.html

相关文档

  • 去漂流晒黑了怎么办漂流后晒黑了怎么白回来2018
  • 陈果和叶修有感情线吗全职高手陈果会不会和叶修在一起
  • 幼儿园争创市五四青年先进集体事迹材料
  • 民间借条几年之内有法律效应
  • 人们用英语怎么说
  • 嫁给你是我的幸娶了我却不是你的运杂文随笔
  • 区块链中密码学与安全技术
  • 有关于@GetMapping与@RequestMapping
  • 造价授权委托书
  • 2020年—2021年第一学期学生会工作总结
  • 必看!2016年5月英语六级口语考前练习
  • 恒波手机可靠谱吗
  • 人生如屋信念是柱--学习吴大观同志先进事迹
  • 100克红薯多大
  • 安装Ubuntu1804+cuda10.1+cudnn7.5.1流程
  • 云上快报 | 混合云全线产品强势入选Gartner【中国云基础设施和平台服务市场指南】
  • 美式乡村混搭风设计效果图
  • ps怎么把白色的去掉
  • ID移除对方还能正常使用吗
  • 宝宝总是拿手揉眼睛是怎么了?宝宝眼睛痒怎么处理?
  • 此AppleID已由于安全原因被禁用该怎么解决
  • 文明礼仪规范演讲词内容
  • 伤感说说句子带图片
  • 2020年北京出版专业资格考试报名条件
  • 《餐桌上的谜底》阅读答案
  • 不能和羊肉一起吃的食物
  • 夏季高温常识
  • LeetCode简单动态规划题之打家劫舍
  • (精品)教学计划集合7篇
  • 反转校园神秘微机室
  • 猜你喜欢

  • SVN 撤回(回滚)提交的代码
  • 2016考研常识:考研需满足的五大条件
  • 【精华】过生日作文500字集锦6篇
  • 2020年五年级下册数学习题课件-第一、二单元达标检测卷|人教新课标 (共12张PPT)
  • 安全生产规章制度管理办法
  • 3.2 千米的认识
  • 四川2017年硕士研究生招生考试现场确认公告
  • 初中音乐人教版九年级下册第三单元《唱歌 绿袖子》优质课教案省级比赛获奖教案公开课教师面试试讲教案
  • 三年级期末考试后的反思作文
  • 2015年度浙江盛达纺织服装有限公司销售收入与资产数据报告
  • 厦门市机动车驾驶员培训机构教学车辆新增申请表
  • 度米作文汇编之人教版七年级下册五单元作文范文金星探险记
  • 初二写人作文:新闻人物_800字
  • 六一儿童节幼儿讲话稿
  • 八年级英语上册Unit1Wheredidyougoonvacation第4课时SectionB2a_2e同步测试人教新目标版
  • 夏季吃茄子有什么坏处
  • 人美版美术六上《家乡的艺术》教案反思评课
  • 【最新2018】清明节祭扫烈士墓仪式上的讲话-实用word文档 (1页)
  • 优化方案2017高中数学 第一章 三角函数 1.4.1 正弦函数、余弦函数的图象新人教A版必修4
  • 新员工入职基础培训教材(共38张PPT)
  • 改良小骨窗手术治疗基底节区高血压性脑出血体会
  • 暴雨来临
  • 小议如何有效防范公务卡支付结算使用中的风险
  • 厦门市勤安居房地产营销策划有限公司企业信用报告-天眼查
  • 德育常规自查评分表
  • 安徽省长丰县高中联考2018-2019学年英语(含五份模拟)高二下学期期末模拟试卷
  • 2018年高三最新 福建高考数学秘籍18法2018数学填空题的常用解法2018201823 精品
  • 女性绝经的原因有哪些 绝经的病因是什么
  • 液压支架工技能鉴定试题0
  • 2018年秋七年级科学上册 第2章 观察生物 第4节 常见的动物 第3课时 常见的无脊椎动物教案 (新版)浙教版
  • 初中生物_基因在亲子代间的传递PPT课件9
  • 工作总结-房地产销售年终总结范例 精品
  • 【最新自查报告范文范本模板】学院“三提升”活动对标定位报告
  • 八年级日记350字:妈妈的节日
  • 海丰县政府财贸办公室企业信用报告-天眼查
  • zabbix中添加主机时主机名的命名
  • 森林防火学生致家长的一封信
  • 基于形状特征变化的凋亡细胞图像识别研究
  • 陶醉在重阳
  • 《爱在左,感恩在右》主题班会教案
  • 饮食营养与健康教案
  • 8下Unit2 Travelling 复*课件(县公开课课件共19张PPT)
  • 电脑版