`
lanqiu17
  • 浏览: 17715 次
社区版块
存档分类
最新评论

简单的归并排序

阅读更多

额。。。 我发现一直写数据结构的可能有点枯燥。 于是我准备开始写点我常用的算法。再说,复杂的我也不会

今天,我就写个简单的归并排序。本来想写冒泡或者选择排序的。但写的时候,很好就完了,于是决定写点有意思的排序算法。

 

归并排序,熟悉排序算法的都应该不会陌生吧。 因此,我就不讲一堆理论(其实,我也不太清楚)。总之,了解归并排序的核心思想就对了。 当然,还是使用python实现。因为我最近在学python啊。感觉python很有意思

如有问题,请指正。

代码如下:

# -*- coding: cp936 -*-
#---------------------------------------------
#                                             
#author   chile                                    
#version  1.0                                  
#since                                        
#date   2014-02-18                                   
#desc  归并排序                                       
#                                            
#                                            
#                                             
#---------------------------------------------

class MergeSort:
    def __init__(self):
        self.src = []
        self.help  = []
    
    def sort(self,src):
        if len(src) == 0:
            return
        self.src = src
        self.initTarget()
        low , high = 0 , len(src) - 1
        self.megersort(low,high)
    
    #由于python中数组是动态型的,需要手动初始化
    def initTarget(self):
        target = self.help
        for i in range(len(self.src)):
            target.append(0)
    
    #递归调用 
    def megersort(self,low,high):
        if low >= high:
            return
        mid = low + (high - low ) / 2
        self.megersort(low,mid)
        self.megersort(mid+1,high)
        self.merge(low,mid,high)
    
    #核心方法 (归并排序的思想是,当只有一个时,那个这个数就是有序的)
    def merge(self,low ,mid , high):
        src , help = self.src , self.help 
        for i in range(low,high+1):
            help[i] = src[i]
        
        i , j = low , mid + 1
        for k in range(low,high + 1):
            if i > mid:
                src[k] = help[j]
                j += 1
            elif j > high:
                src[k] = help[i]
                i += 1
            elif help[i] < help[j]:
                src[k] = help[i]
                i += 1
            else:
                src[k] = help[j]
                j += 1
                
                
val = range(15,2,-1)
print val 
sort = MergeSort()
sort.sort(val)
print sort.src  
                
                

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics