从那里说起好咧?

从那里说起好咧?

我也不知道从那里说好,也不知道标题是什么?

也不知道从那里蹦出来的想法:数字的排序用什么方法好点?

请原谅我还在想这么初级的问题,我的数据结构和算法确实很烂,不能说烂,是基本就搞不清楚。

给自己找借口(当时上数据结构的时候,我连属于自己的电脑都没有。)其实,就是自己脑子笨。。。。

好。一张白纸反而跟容易画画。

我的自觉告诉我了一个方法:

依次把元素和她右边的所有元素进行比较,大于右边(从小到大 排序)的就把两个元素的位置交换(python 的操作就比较简单,而且直观

a,b = b,a),遍历整个数组就可以了。

于是就用python实现了一下,很顺利,没有问题。

可是我有问题,开始时,对于具体的数组操作有些模糊没有画面感,于是对每个操作都输出一下,来清楚到底是这么比较的,瞧我多笨。还有冒失排序方法是有名字的,这个方法叫什么名字咧?难道是我第一个想出来的?

google 了下排序算法 ,原来叫 冒泡排序,是说我怎么这么熟悉咧?

想起来了,那是上个夏天,右手骨折,快两个月没去上课,当然去没去都是一回事。期末考试也没去考。中途还交了一次 网页设计 的作业,单手敲代码纯手工完成,好有自豪感有木有!可是又能怎样咧!说远了。那个万般无赖的夏天,捧着JAVA书看,那时候我居然看JAVA(我绝对不歧视其他编程语言,包括JAVA),废话要考试的。然后对着两个for循环看了一下午,一下午……我没睡着吧……也就是一个冒泡排序。

当然 冒泡排序 有他的优点,实现简单 逻辑清晰,缺点就是元素的比较和交换的次数比较多,相对较慢,简单的说就是效率比较低。

冒泡排序说清楚点就是:把第一位的数字分别与他后面的数字进行比较,如果第一位的数字大于后面的任意一个数字就交换顺序,这样就保证了第一位的数字是最小的,依次第二位第三位~~~是最小的,排序完成。

排序算法很多, 每种算法还有各种变形和优化,每种算法都有自己的优缺点,看多了头也大。我就先挑了 快速排序 来看。

看了一些 快速排序 的文字描述,越看越模糊,始终没搞明白过程是怎样的,有人说是这样,又有人说是那样,怎么都不一样?

也看了些语言的实现,越看越模糊越看越啰嗦,当我看了wiki 上快速排序的 python 例子,自己实现了下就明白了。

使用的是 递归 加上列表解析,让过程变的简单。因为递归将一个看似复杂繁琐的过程分解成了一个个简单并且相同的小问题,与 for 循环 不同的是,

for 更像是层叠,一层叠一层,爬完一层楼派下一层楼。而递归更像是大圆中有小圆,小圆中还有更小的圆,细胞分裂的感觉。

那快速排序到底该怎么做咧?                      快速排序用了二分法,这个世界上的任何数去不断除以二最后都无限接近于零

我们把排序的步骤分解,步骤都是相同的就是,取出数组的一个数设为标杆(为了方便,我就选数组的第一个数为标杆,因为数组顺序是打乱的,选任意位置的意义其实都是一样的。)数组中小于标杆的数放在标杆的左边,大于的放在右边。(在实现中,小于的放在一个数组中,大于的放在另一个数组中,最后和标杆一起拼接成完整的排序完成的数组),虽然左边的数都小于右边的,但是左边和右边的单独的排序都没有完成呀。这就要递归调用一下就可以了,因为排序的步骤依旧是一样的,标杆,左边,右边,递归到最后分解到最小的元素,整个数组的排序也就完成了。

虽然对于人类的线性思维,需要拐个弯,这种发散性的对于电脑来说内部循环可以有效地被实现出来。

看似递归很简单,但是也要控制好递归的边界,要让递归有个停止的边界,否则越滚越大就不好收场了。

说了这么多,上代码!代码看不明白就不要看了,仔细想一下过程,试着自己实现一下就好。

    import random 
    
    # 生成随机数组

    num = []
    for x in xrange(0,10):
        num.append(random.randint(0,100))
    length = len(num)
    print num,':',length
    
    
    ########## Bubble ##########

    def Bubble(num):
        count = 0
        for i in xrange(length-1):
            print '='*5,'Round:%d' %i,'='*5 
    	for x in xrange(1,length-i):
    	    #count

    	    count+=1
    	    # compare

    	    if num[i]>num[i+x]:
    	        num[i],num[i+x] = num[i+x],num[i]
    		# print

    		print x,':',num
        
        print '\ncount:%d' %count
        return num
    print Bubble(num)
    
    ############ quick ##########

    def quick(num):
        if not num:return []
        return quick([ x for x in num[1:] if x <= num[0] ]) +num[0:1]+ quick([ x for x in num[1:] if x > num[0] ])
    
    print quick(num)

javascript 快排

    
    var arr = [];
    for(var i=0;i<10;i++){
    	arr.push(Math.floor(Math.random()*100))
    }
    console.log(arr)
    
    function quick(arr){
    	if (arr == false) {
    		return []
    	};
    	var left=[],
    		right=[];
    	for( var i = 1; i<arr.length;i++){
    		if( arr[i] <= arr[0]){
    			left.push(arr[i])
    		}else{
    			right.push(arr[i])
    		}		
    	};
    	return quick(left).concat(arr[0],quick(right))
    }
    
    quick(arr)

先这样把,其他的再说

http://www.cs.usfca.edu/~galles/visualization/Algorithms.html http://www.luocong.com/dsaanotes/index-Z-H-2.htm

Tag:javascriptpython冒泡排序快速排序排序算法 Published under (CC) BY-NC-SA
comments powered by Disqus