1 / 16
文档名称:

常见排序算法总结.doc

格式:doc   页数:16页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

常见排序算法总结.doc

上传人:pk5235 2015/6/30 文件大小:0 KB

下载得到文件列表

常见排序算法总结.doc

相关文档

文档介绍

文档介绍:常见排序算法总结【转载+整合】
2009-09-14 15:17
1、稳定排序和非稳定排序
简单地说就是所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,我们就说这种排序方法是稳定的。反之,就是非稳定的。要注意的是,排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。
比如:一组数排序前是a1,a2,a3,a4,a5,其中a2=a4,经过某种排序后为a1,a2,a4,a3,a5,则我们说这种排序是稳定的,因为a2排序前在a4的前面,排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。
2、内排序和外排序
在排序过程中,所有需要排序的数都在内存,并在内存中调整它们的存储顺序,称为内排序;
在排序过程中,只有部分数被调入内存,并借助内存调整数在外存中的存放顺序排序方法称为外排序。
3、算法的时间复杂度和空间复杂度
所谓算法的时间复杂度,是指执行算法所需要的计算工作量。
一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。
=======================================

首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。
从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。
重复2号步骤,直至原数列为空。
插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。
①.直接插入排序(稳定)
     接插入排序的过程为:在插入第i个记录时,R1,R2,..Ri-1已经排好序,将第i个记录的排序码Ki依次和R1,R2,..,Ri-1的排序码逐个进行比较,找到适当的位置。使用直接插入排序,对于具有n个记录的文件,要进行n-1趟排序。
代码如下:
void Dir_Insert(int A[],int N)   //直接插入排序
{
     int j,t;
     for(int i=1;i<N;i++)
     {
         t=A[i];
         j=i-1;
         while(A[j]>t)
         {
             A[j+1]=A[j];
             j--;
         }
         A[j+1]=t;
     }
}
②.希尔排序(不稳定):
     希尔(Shell)排序的基本思想是:先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取得第二个增量d2<d1重复上述的分组和排序,直至所取的增量di=1,即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
     一般取d1=n/2,di
+1=di/2。如果结果为偶数,则加1,保证di为奇数。
     希尔排序是不稳定的,希尔排序的执行时间依赖于增量序列,其平均时间复杂度为O(n^).
代码如下:
void Shell(int A[],int n)   //Shell排序
{
     int i,j,k,t;
     (n/2)%2 == 0 ? k = n/2+1 : k = n/2; //保证增量为奇数
     while(k > 0)
     {
         for(j=k;j<n; j++)
         {
             t = A[j];
             i = j - k;
             while(i>=0 && A[i]>t)
             {
                 A[i+k]=

最近更新

内蒙古2018版保育员初级考试试题试卷及答案 11页

内蒙古2018年保育员三级专业能力考试试题试卷.. 10页

关爱留守儿童暑期社会实践心得体会与关爱留守.. 16页

关于读书活动心得体会与关于读书演讲稿汇编 7页

交警大队开展交通安全隐患排查整治工作总结与.. 5页

云南省2020版保育员四级业务能力考试试题试卷.. 11页

2020版幼儿园小班保育员上学期考试试题试卷及.. 10页

2025年度奶茶店员工劳动合同解除备案与执行合.. 8页

2025年度夫妻忠诚协议及出轨赔偿条款合同 7页

2025年度太阳能设备维修服务委托协议 8页

2025年度大连正规房产买卖合同毁约处理细则 8页

2025年度大学生实习实训项目实习实训基地建设.. 9页

2025年度大型挂车租赁及全程物流跟踪服务合同.. 8页

2025年度外贸企业供应链金融合作协议书 8页

2025年度塑料管材防腐蚀性能购销合同 9页

2025年度城市综合体停车位使用权转让协议 7页

2025年度城市文化旅游节庆活动宣传策划合同 9页

2025年度城市地下管线探测与修复劳务合同承担.. 9页

2025年度城乡供水一体化项目供用水合同模板 9页

2025年度地基房屋买卖及配套设施管理合作协议.. 10页

2025年度地下室房屋租赁与艺术展览合作合同 8页

2025年度土建工程绿色施工废弃物处理合同 9页

2025年度土地流转居间与农业生态循环经济发展.. 9页

2025年度土地厂房租赁合同:航空航天装备维修.. 8页

2025年度国际贸易实习生合作协议范本 8页

XX学校义务教育优质均衡发展创建实施方案范文.. 8页

顺丁烯二酸酐工艺规程 25页

节后复工复产安全生产培训记录 6页

核电知识竞赛试题及答案 7页

(LARS)评价量表 1页