几种常用的排序算法

几种常用的排序算法

ID:25381660

大小:77.18 KB

页数:4页

时间:2018-11-20

几种常用的排序算法_第1页
几种常用的排序算法_第2页
几种常用的排序算法_第3页
几种常用的排序算法_第4页
资源描述:

《几种常用的排序算法》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、几种常用的排序算法(转载收藏)2009-03-0623:161选择排序先在整个序列中选出关键字值最小的元素,如果它不是第一个元素,则将它和第一个元素交换;然后在除一个除第一个位置上的元素以外的其余元素中再选出关键值次最小的元素,如果它不在第二个位置,则和第二个位置上的元素进行交换;依次类推,直至所有元素排序完成.该算法是不稳定的.[1]算法:选择排序Algorithmselect_sort(s[])//s[]为sortseq型排序表,n为整型常量//i,j,k为整型//t为元素类型{For(i=1;i<=n-1;++i){k=I;for(j=i+1;j<=n;++j)if(s[j]

2、.key

3、插完.该算法是稳定的算法;直接插入排序Algorithminsert_sort(s[])//s[]为sortseq型排序表,n为整型常量//i,j为整型{for(i=2;i<=n;++i){s[0]=s[i];for(j=i–1;s[j].key>s[0].key;--j)s[j+1]=s[j];s[j+1]=s[0];}}2)对半插入排序直接插入排序中,将查找第i个元素插入位置的方法改用对半法进行关键字间的比较,便得到对半插入排序.为了用对半法查找插入位置,待排序的n个元素序列的存储结构须采用顺序存储方式.该算法是稳定的.算法:对半插入排序algoreithmbin_sort(s

4、[]){for(i=2;i<=n;++i){s[0]=s[i];L=1;h=i–L;while(L<=h){m=(L+h)/2;if(s[m].key>s[0].key)h=m–1;elseL=m+1;}for(j=i–1;j>=1;--j)s[j+1]=s[j];s[L]=[0];}}注:本文用大写L以区别小写l与数字1的区别3冒泡排序先将第一个元素的关键字和第二个元素的关键字进行比较,若不满足顺序要求,则将两个元素进行交换;然后比较第二个和第三个元素的关键字并作同样处理;依次类推,直至第n-1个元素的位置和第n个元素进行比较并处理完.这时关键字值最大的元素被交换到最后一个元素的

5、位置上,这是一趟排序过程.重复执行这种运算过程,不过第2趟只需对前n-1个元素进行排序,第3趟只需对前n-2个元素进行排序,如此下去,直至在一趟排序中没有元素进行过交换或最多进行了n-1趟排序为止.算法:冒泡排序algorithmbubble_sort([])//s[]为sortseq型排序表,n为整型常量//i,j,done为整型//temp为元素类型{i=1;done=0;while(i<=n–1&&!done){done=1;for(j=1;j<=n–i;++j)if(s[j].key>s[j+1].key){done=0;temp=s[j];s[j]=s[j+1];s[j+

6、1]=tem[;}++i;}}4快速排序从排序过程来看,快速排序与冒泡排序一样,也是通过元素交换方式来进行排序的.快速排序方法的基本思想是:在待排序的元素序列中任取一个元素(例如取第一个元素),通过一趟排序,以该元素的关键字为标准,将待排元素序列分成两部分,所有关键不大于该元素关键字的元素排在它的位置之前(即左边),所有关键字不小于该元素关键字的元素排在它的位置之后(即右边),把该元素排在这两部分的中间,这就是该元素最终排序的位置.然后分别对这两部分重复上述排序,直至所有的元素都排到序列的相应位置上为止.该算法是不稳定的算法:快速排序.algorithmquick_sort(s[]

7、,L,r)//s[]为sortseq型排序表//L,j,r为整型//k为keytype型//temp为元素型{if(L=k&&ij){s[i++]=s[j];while(s[i].key<=k&&i

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。