论坛 › Python › [硕.Love Python] MergeSort(归并排序)

zzgzyyz 发表于 2018-8-15 11:34:20

[硕.Love Python] MergeSort(归并排序)

　　
def merge(s, d, i, m, n):
　　
    # merge [i, m) [m, n)
　　
    j, k = m, i
　　

　　
    while i < m and j < n:
　　
      if s < s:
　　
            d = s
　　
            i += 1
　　
      else:
　　
            d = s
　　
            j += 1
　　
      k += 1
　　

　　
    while i < m:
　　
      d = s
　　
      i += 1
　　
      k += 1
　　

　　
    while j < n:
　　
      d = s
　　
      j += 1
　　
      k += 1
　　

　　
def mergeOnePass(s, d, mlen):
　　
    i, n = 0, len(s)
　　
    while i + 2 * mlen <= n:
　　
      merge(s, d, i, i + mlen, i + 2 * mlen)
　　
      i += 2 * mlen
　　

　　
    if i + mlen < n:
　　
      merge(s, d, i, i + mlen, n)
　　
    else:
　　
      for i in xrange(i, n):
　　
            d = s
　　

　　
def mergeSort(s):
　　
    tmp = s[:]
　　

　　
    mlen, n = 1, len(s)
　　
    while mlen < n:
　　
      mergeOnePass(s, tmp, mlen)
　　
      mlen *= 2
　　
      mergeOnePass(tmp, s, mlen)
　　
      mlen *= 2
　　

　　
if __name__ == '__main__':
　　
    from random import shuffle
　　
    s = range(100)
　　
    shuffle(s)
　　
    print s
　　
    mergeSort(s)
　　
    print s

查看完整版本: [硕.Love Python] MergeSort(归并排序)