Chinaunix首页 | 论坛 | 博客
  • 博客访问: 135345
  • 博文数量: 25
  • 博客积分: 588
  • 博客等级: 中士
  • 技术积分: 292
  • 用 户 组: 普通用户
  • 注册时间: 2011-01-10 18:18
文章分类

全部博文(25)

文章存档

2012年(7)

2011年(18)

我的朋友

分类: Python/Ruby

2011-03-05 12:59:24

import sys
def merge(a, b, l, m, r):
    i = l
    k = l
    j = m + 1
    while i <= m and j <= r:
        if a[i] <= a[j]:
            b[k] = a[i]
            i += 1
        else:
            b[k] = a[j]
            j += 1
        k += 1
    if i > m:
        while j<=r:
            b[k] = a[j]
            k += 1
            j += 1
    if j > r:
        while i<=m:
            b[k] = a[i]
            k += 1
            i += 1
    #copy to a
    i = l
    while i<= r:
        a[i] = b[i]
        i += 1   
    pass
def mergeSort(a, l, r):
    if l>=r:
        return
    m = (l+r)/2
    mergeSort(a,l,m)
    mergeSort(a,m+1,r)   
    merge(a,b,l,m,r)
def mergeSort2(a, n):
    s = 2
    while s < n:
        i = 0
        while i <= n - 2*s:
            merge(a,b, i, i+s-1, i+2*s-1)
            i += 2*s
        s += s
if __name__ == '__main__':
   
    a = [3, 5, 6, 10, 2, 7, 4, 20, 1, 100, 99 ,45, 60]
    length = len(a)
    b = [0] * length   
   
    try:
        mergeSort(a, 0, length-1)
        mergeSort2(a, length-1)
    except Exception,e:
        print e
    print a
   
   
   
   
       
        
   
   
阅读(1514) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~