简单的归并排序

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

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

 

归并排序，熟悉排序算法的都应该不会陌生吧。 因此，我就不讲一堆理论（其实，我也不太清楚）。总之，了解归并排序的核心思想就对了。 当然，还是使用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