分享
 
 
 

Coco学编程(二)--直接选择排序

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

Coco:这么长时间不来,我还真想大家,实在是某人太懒了,总也不来上课。

我:这个……还真是对不起啊。主要是因为最近找了份新工作,正在赶一个项目,比较忙一些。经常会有天黑才回来的事情,所以有很长一段时间没有出现。

Coco:据我所知~某人天黑才会回家,是因为在广州总迷路,每次坐在车上的时间还没有找路的时间长,而且,还因为一些很菜的程序问题被卡住了……

我:为什么总要揭我的短呀……-_-#

Coco:hoho,上课上课~

我:好吧,上次讲了直接插入排序,我们从改进它开始。这几天,你对这个算法有什么想法没有?

Coco:在书上读到,在容器中反复的插入和删除节点是一种很低效的做法,不但速度慢,还会造成内存的碎片化,是这样子的吧。

我:很正确,所以通常来说,我们应该想办法减少插入和删除的次数。这样可以有效避免内存的碎片化。

Coco:不过对于选择插入法来说,我们只移动出现逆序的节点了,还有什么办法能更进一步减少这插入和删除的操作吗?

我:有一个办法,就是不用del和Insert进行显示的删除和插入操作,充分利用容器现有的空间,以交换节点来移动它。

Coco:不太理解。

我:由些产生的最简单的方法,用简单的数学描述来讲,是这样子的,假设集合有{a1, a2, a3,…, an},我们先从整个区间中找出最小的一个元素am,如果它不等于a1,就把它和a1交换;然后查找[a2, a3,…, an]区间,在其中找出最小的元素,如果它不等于a2,就把它和a2交换;重复这一过程,就可以对整个数组排序了。

Coco:看起来很简单呀,我去试试,测试代码段就还用上次的喽~

#以下是Coco的代码:

#Direct choice sort. It is a sample method.

def DrtChcSort(theArray):

#Move the begin of search area.

for i in range(len(Array)):

curMrk = i

#Find the min node.

for j in range(i, len(theArray)):

if theArray[j] < theArray[curMrk]:

curMrk = j

#Move it to front.

if not(curMrk == i):

theArray[curMrk], theArray[i] = theArray[i], theArray[curMrk]

Array=[6,16,10,9,15,5,11,1,19,4,14,18,0,13,3,17,12,2,8,7]

print Array

DrtChcSort(Array)

print Array

Coco:这办法比上次那个简单多了嘛,为什么当初不教我这个?

我:要你写这些算法又不是真要你实用,主要是练习一下。要不然,对python的数组排序最简单的办法应该是:Array.sort()

Coco:倒~好吧,算你说的有道理,不过这样直接交换链表中的元素:“theArray[curMrk], theArray[i] = theArray[i], theArray[curMrk]”真的可以保证内存不会碎片化,还能减少插入和删除吗?

我:老实说,我不知道,因为python对这个线性容器的操作被封装了起来,从我们这个使用层上,是看不到的。不过,我们至少避免了显示的增删操作。如果说这样编程是“可能会有坏结果”,那显示的增删操作则是“几乎一定会有坏结果”,如果在C语言这类直接操作内存的语言中,两者的效果就是很明确的了。

Coco:为什么说“几乎”?

我:因为python有它的内存管理机制,它可以进行垃圾回收,所以内存的碎片化和丢失,还是会受到控制,特别是jython,由于使用java平台,基本上不存在内存方面的困扰。不过,过于依赖它也不是好主意,至少会给虚拟机带来不必要的负担。

Coco:听起来有道理的样子,我还有一个疑问,在这个排序中,我们把当前已排序间后面的那个元素直接与未排序区间中的最小元素交换了,这会不会造成后面的未排序区间越来越乱,给我们带来额外的麻烦呢?

我:这种交换的确有增加混乱――形像的说,就像热学中的“熵”――的可能,不过如果这个算法只考虑某一个链表,也就基本上没有什么用途了。而从统计角度讲,未排序区间的“熵”

不会因此而增加。

Coco:明白了,不过这个算法太简单了,再多讲点东西吧。

我:上次有个朋友问递归的含义,你知道吗?

Coco:递推多项式,一种表达式,每一项由前一项使用的公式来决定。

我:怎么看着这么眼熟啊,从哪里贴来的?

Coco:这么快就让你看出来了啊,《金山词霸》喽~

我:倒……真会偷懒,简单的说,递归的就是指一个方法中会使用它自身。

Coco:听起来怪怪的,给个程序让我们看看吧。

我:欧几里德算法,辗转相除求最大公因子,如何?你来写这个程序吧,也不是多难

Coco:真会偷懒~

def Gba(a, b):

r = a%b

if r == 0:

return b

else:

return (b, r)

Coco:调用这个函数就可以得到a和b的最大公因子了。这种通过调用自身来进入下一步的函数就是一种递归函数吧。

我:是的,与之相对应的运算方法是迭代,也就是说通过某种方法重新记录当前状态,然后循环生成这一状态的算法,这样不用重复调用函数,在效率上比递归要好,不过可读性通常会差一些。比如以上这个Gba(a, b)的递归形式应该是这样子:

def Gba(a, b):

r = a%b

while r!=0:

a, b = b, r

r = a%b

return b

Coco:好像明白点儿了。接下来呢?

我:上次去cn99新闻组上问你说的那个很菜的问题时,有位叫Chad Netzer的朋友写了一个不错的回应,虽然我的问题很菜(Coco:这个笨蛋会不知道在python里怎么交换元素,也敢出来教别人,我真是遇人不淑呀~),但这位朋友写的回信比我的问题更有价值,如果明天有空,我把它译出来给大家分享一下。不过今天先这样吧,这两天感冒,不太舒服,明天还要上班。

Coco:感冒了不早说,别传染给我,闪~

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有