Coco学编程（二）－－直接选择排序

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

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

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

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

Coco：hoho，上课上课～

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

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

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

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

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

Coco：不太理解。

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

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：感冒了不早说，别传染给我，闪～