设为首页 - 加入收藏
广告 1000x90
您的当前位置:黄大仙www78345 > 交换排序 > 正文

三值的排序

来源:未知 编辑:admin 时间:2019-06-11

  排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是,当我们给某项竞赛的优胜者按金银铜牌序的时候。

  在这个任务中可能的值只有三种1,2和3。我们用交换的方法把他排成升序的。

  写一个程序计算出,给定的一个1,2,3组成的数字序列,排成升序所需的最少交换次数。

  请付上思路和带注释的程序(Pascal),谢谢.展开我来答

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  有一个由N个数值均为1、2或3的数构成的序列(N= 1000),其值无序,现要求你用最少的交换次数将序列按升序顺序排列。

  算法:排序后的序列分为三个部分:排序后应存储1的部分,排序后应存储2的部分和排序后应存储3的部分,贪心排序法应交换尽量多的交换后位置正确的(2,1)、(3,1)和(3,2)数对。当这些数对交换完毕后,再交换进行两次交换后位置正确的(1,2,3)三个数。

  分析:很明显,每一次交换都可以改变两个数的位置,若经过一次交换以后,两个数的位置都由错误变为了正确,那么它必定最优。同时我们还可发现,经过两次交换后,我们可以随意改变3个数的位置。那么如果存在三个数恰好为1,2和3,且位置都是错误的,那么进行两次交换使它们位置正确也必定最优。有由于该题具有最优子结构性质,我们的贪心算法成立

本文链接:http://apkhealth.com/jiaohuanpaixu/326.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top