丹麦签证中心地址:小结主要排序算法 - 子 孑 - 51CTO技术博客

来源:百度文库 编辑:偶看新闻 时间:2024/04/28 14:40:32
博客登录
用户名:
密 码:

注册 |登录忘记密码?51cto首页 |博客 |论坛 |招聘 热点文章跟我学交换机配置(五)

帮助
转载:0
翻译:6
原创:125
 子 孑  
http://zhangjunhd.blog.51cto.com >复制链接邀请加入技术圈
加友情链接
发短消息
相册
技术圈
博客
51CTO首页 |技术论坛 |短消息

博 客
我的博客发表文章管理博客
技术圈
创建圈子我的圈子寻找圈子
相 册
我的相册上传图片管理相册
首页 |随笔 |代码 |模式 |数据结构/算法 |语言 |系统 |网络/分布式 |软件工程 |持久化 |资源 |部署 |框架 |组件 |UI |并发 |Web
金秋九月,博客No.1的荣誉属于你我  51CTO博客急招兼职 博主的更多文章>>
小结主要排序算法
2008-09-28 20:49:08
标签:算法排序   [推送到技术圈]
版权声明:原创作品,允许转载,转载时请务必以超链接形式标明文章原始出处 、作者信息和本声明。否则将追究法律责任。http://zhangjunhd.blog.51cto.com/113473/102754
1.插入排序-O(N2)
插入排序由N-1趟排序组成。对于P=1趟和P=N-1趟,插入排序保证从位置0到位置P上的元素为已排序状态。
typedef int ElementType;
void Swap( ElementType *Lhs, ElementType *Rhs )
{
ElementType Tmp = *Lhs;
*Lhs = *Rhs;
*Rhs = Tmp;
}
/* 插入排序 */
void InsertionSort( ElementType A[ ], int N )
{
int j, P;
ElementType Tmp;
for( P = 1; P < N; P++ )
{
Tmp = A[ P ];
for( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- )
A[ j ] = A[ j - 1 ];
A[ j ] = Tmp;
}
}
2.希尔排序-O(N2)
希尔排序使用一个增量序列h1,h2,...,ht,其中h1=1。每次选择ht,ht-1,..,h1进行排序,对于每个增量hk排序后,有A[i]<=A[i+hk],即所有相隔hk的元素都被排序。希尔排序的实质是执行多趟间隔为hk的元素间的插入排序。
/* 希尔排序 */
void Shellsort( ElementType A[ ], int N )
{
int i, j, Increment;
ElementType Tmp;
for( Increment = N / 2; Increment > 0; Increment /= 2 )
for( i = Increment; i < N; i++ )
{
Tmp = A[ i ];
for( j = i; j >= Increment; j -= Increment )
if( Tmp < A[ j - Increment ] )
A[ j ] = A[ j - Increment ];
else
break;
A[ j ] = Tmp;
}
}
3.堆排序-O(NlogN)
堆排序由两个过程组成,一是建堆-O(N),二是N-1次删除堆顶元素-O(NlogN)。
建堆(大顶堆)过程为,由完全二叉树的最后一个非叶节点(秩为(N-2)/2)开始执行下滤操作,直到堆顶元素为止。删除堆顶元素过程为,将堆顶元素与数组末尾元素互换,新的二叉堆(除去数组后端被置换出的堆顶元素),再次执行堆顶元素的下滤操作。如此循环,直到堆中只有一个元素。此时,排序完成。此排序无需额外空间,为就地排序。
#define LeftChild( i )    ( 2 * ( i ) + 1 )
/* 下滤过程,构建大顶堆 */
void PercDown( ElementType A[ ], int i, int N )
{
int Child;
ElementType Tmp;
for( Tmp = A[ i ]; LeftChild( i ) < N; i = Child )
{
Child = LeftChild( i );
if( Child != N - 1 && A[ Child + 1 ] > A[ Child ] )
Child++;
if( Tmp < A[ Child ] )
A[ i ] = A[ Child ];
else
break;
}
A[ i ] =Tmp;
}
/* 就地堆排序 */
void Heapsort( ElementType A[ ], int N )
{
int i;
for( i = (N - 2) / 2; i >= 0; i-- )    /* BuildHeap */
PercDown( A, i, N );
for( i = N - 1; i > 0; i-- )
{
Swap( &A[ 0 ], &A[ i ] );    /* DeleteMax */
PercDown( A, 0, i );
}
}
4.归并排序-O(NlogN)
归并排序实质是将序列分成左右两个子序列,分别排序,然后再合并成一个有序序列。
/* Lpos = start of left half, Rpos = start of right half */
void Merge( ElementType A[ ], ElementType TmpArray[ ], int Lpos, int Rpos, int RightEnd )
{
int i, LeftEnd, NumElements, TmpPos;
LeftEnd = Rpos - 1;
TmpPos = Lpos;
NumElements = RightEnd - Lpos + 1;
/* main loop */
while( Lpos <= LeftEnd && Rpos <= RightEnd )
if( A[ Lpos ] <= A[ Rpos ] )
TmpArray[ TmpPos++ ] = A[ Lpos++ ];
else
TmpArray[ TmpPos++ ] = A[ Rpos++ ];
while( Lpos <= LeftEnd )    /* Copy rest of first half */
TmpArray[ TmpPos++ ] = A[ Lpos++ ];
while( Rpos <= RightEnd ) /* Copy rest of second half */
TmpArray[ TmpPos++ ] = A[ Rpos++ ];
/* Copy TmpArray back */
for( i = 0; i < NumElements; i++, RightEnd-- )
A[ RightEnd ] = TmpArray[ RightEnd ];
}
void MSort( ElementType A[ ], ElementType TmpArray[ ], int Left, int Right )
{
int Center;
if( Left < Right )
{
Center = ( Left + Right ) / 2;
MSort( A, TmpArray, Left, Center );
MSort( A, TmpArray, Center + 1, Right );
Merge( A, TmpArray, Left, Center + 1, Right );
}
}
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 Merge()函数合并两个有序子序列;
void MSort()归并排序递归实现,递归基是Left>=Right,此时序列中只有一个元素;
void Mergesort()分配空间,调用归并函数,释放空间。
5.快速排序-O(NlogN)
设数组S,快速排序为quicksoet(S),算法为,
1.如果S中元素个数是0或1,则返回;
2.取S中任一元素v,称之为枢纽元(pivot);
3.将S-{v}(S中其余元素)分成两个不相交的集合;分别为大于等于v的元素集S1和小于等于v的元素集S2;
4.递归实现quicksort(S1)和quicksort(S2)。
/* Return median of Left, Center, and Right */
/* Order these and hide the pivot */
ElementType Median3( ElementType A[ ], int Left, int Right )
{
int 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 ] );
/* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */
Swap( &A[ Center ], &A[ Right - 1 ] );    /* Hide pivot */
return A[ Right - 1 ];                                /* Return pivot */
}
#define Cutoff ( 3 )
void Qsort( ElementType A[ ], 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 */
Qsort( A, Left, i - 1 );
Qsort( A, i + 1, Right );
}
else    /* Do an insertion sort on the subarray */
InsertionSort( A + Left, Right - Left + 1 );
}
void Quicksort( ElementType A[ ], int N )
{
Qsort( A, 0, N - 1 );
}
使用Median3()函数选取枢纽元,这是三数中值分割法,对于数组S的N-1个元素,取S[0],S[N-1],S[(N-1)/2]三个数中的中位数作为枢纽元。它还完成了第一次比较,即将三者中最小值放在数组最左端,最大值放在数组最右端,中间值即枢纽元放在数组靠右第二的位置并返回之。
对于只有小于等于Cufoff个的序列,实行插入排序,因为对于很小的数组,快速排序不如插入排序。
每次调整后,都能确定枢纽元的位置,该位置在序列中是稳定的,即为排序后最终位置,可以利用这一点构造寻找数组中第k小数的算法,即快速选择算法,该算法的平均花费为O(N)。算法具体为,每次确定枢纽元的位置i后,与k比较,如果k=i+1,则寻找成功,如果k<=i,则继续在前半部分寻找,否则在后半部分寻找。
/* Places the kth smallest element in the kth position */
/* Because arrays start at 0, this will be index k-1 */
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, Right );
}
else    /* Do an insertion sort on the subarray */
InsertionSort( A + Left, Right - Left + 1 );
}
本文出自 “子 孑” 博客,请务必保留此出处http://zhangjunhd.blog.51cto.com/113473/102754
本文出自 51CTO.COM技术博客
上一篇基于队列实现的基数排序  下一篇腾讯,看扁你!
类别:数据结构/算法 ┆技术圈( 1) ┆ 阅读( 1079) ┆ 评论( 3) ┆推送到技术圈 ┆返回首页
相关文章
各种排序算法
排序算法汇总
最优排序算法
基于栈和队列的排序算法
内部排序算法学习
冒泡排序的算法分析与改进
各种排序算法java实现
插入排序
Java 插入排序算法
Java 冒泡排序算法
文章评论
[1楼]      [匿名]yua
2008-09-30 22:08:49
不错的总结。。
短消息通知评论者
[2楼]      leizhimin
2008-10-17 12:45:01
好久没看过算法了。。。。。
博主回复:
java是OO的世界~
2008-11-01 16:06:18
短消息通知评论者
[3楼]      444095567
2008-12-13 18:36:49
算法比较实用
短消息通知评论者
发表评论
昵   称:   快速注册 验证码:点击图片可刷新验证码博客过2级,无需填写验证码
内   容:

zhangjunhd

博客统计信息
51cto博客之星
用户名:zhangjunhd
文章数:131
评论数:462
访问量:352892
无忧币:6256
博客积分:5413
博客等级:8
注册日期:2007-02-03
距离博客争夺赛结束还有21 天
热门文章
基于Tomcat5.0和Axis2开..基于Tomcat5.0和Axis2开..RTP与RTCP协议介绍Apache Commons fileUplo..使用Axis2的底层API开发W..Jsp/Servlet:实现文件上..基于JMF RTP的网络传输媒..Apache Commons-logging..使用Axis2来构建Web Serv..Servlet过滤器介绍之原理..
搜索本博客内文章

我的技术圈(3)
程序设计  开源框架学习站  身边
最近访客
liuch..
unixlab
qingm..
leizh..
风一..
binji..
fjmaplev
dingrily
weili163
yzzh9
最新评论
zhangjunhd:请把感觉转化成code
[匿名]ccw:谢谢,技术流程讲的比较清晰,方便..
[匿名]匿名:感觉不完整,
[匿名]aotian16:thanks
[匿名]peng:很好 值得借鉴 !!!!
[匿名]xi:thx mate
51CTO推荐博文
开源.net开发平台Sharp..VC中文件操作的几种方..SEO是鲨鱼皮而不是螺旋..wxWidgets与其他工具库..Speed Boosting Induct..基于ASP.NET 3.5 Web S..Windows桌面应用程序的..Eclipse CDT环境搭建JAVA版连连看算法研究ASP.NET环境实现多语言..[跟我学嵌入式开发] 驾..
友情链接
小茶的魔法秘室
博远至静
{ :Alex Space =&g..
王春海的博客
maomao
李晨光
时间伙伴
网 文
seven
熔 岩
博客大管家小废物
51cto博客开发
Copyright By 51CTO.COM 版权所有