归并排序

在之前的课堂作业里看到的，就贴了出来，顺便复习一下。

归并与快排都是分治的思想，但是归并多了结果的归并，并且动态的来看，快排是自大而小，即一步一步递归要求子数组有序，归并是自小而大，要求子数组有序，再要求父数组有序。

来自算法4

java版本

• 通用的原地归并的方法
  也可以不原地归并，而是用新的数组以避免过多的元素复制，但是需要在每次递归的时候交换原数组和新数组的角色，应为在同一时刻，只有其中一个是有意义的。

/**
 * 定义一个通用的原地归并的方法
 * 采用元素复制，和 双指针法i，j 分别是左右有序子数组的指针
 */
public static void merge(int[] numbers, int lo , int mid, int hi){

        // 不应该新建数组，而是传入一个和原始数组一样大的数组应用，以避免创建过多的对象
        int[] aux = new int[hi - lo + 1];
        for(int k = lo ; k <= hi ; ++ k){
                aux[k] = numbers[k];
        }
        
        int i = lo , j = mid + 1;

        for(int k = lo ; k <= hi; ++k){
                
                if( i > mid){
                // 左半边用尽
                        numbers[k] = aux[ j ++];
                }else if ( j > hi ){
                // 右半边用尽
                        numbers[k] = aux[ i ++];  
                } else if ( numbers[i] < numbers[j ){
                // 当前左边的元素小于右边的当前元素
                        numbers[k] = aux[ i ++];  
                }else ( j > hi ){
                // 当前左边的元素大于等于右边的当前元素
                        a[k] = aux[ j ++];  
                }
        }
}

• 排序
  1. 递归

  public static void sort(int[] numbers, int lo , int hi){
      if( hi < lo) return;
      int mid = (hi - lo )/2 + lo;
      sort(numbers, lo, mid);
      sort(numbers, mid + 1, hi);
      merge(numbers, lo , mid , hi);
  
  }
  
  

  2. 非递归 自底向上
     两两合并，再四四合并，等等

  static int[] aux ;
  public static void sort(int numbers, int lo , int mid , int i){
      aux = new int[numbers.length];
      int N = numbers.length;
      for(int size = 1;  size < N; size *= 2){
      // size 是 lo 到 hi的一半，所以小于N, 并且，Math.min(lo + size * 2-1 ,N-1), 以避免越界。
              for( int lo = 0; lo < N - size ;  lo += 2 * size){
              merge(numbers, lo , lo + size -1, Math.min(lo + size * 2 -1 , N -1);
              }
      }
  

python版

非递归实现归并排序

import sys

#定义一种通用的原地merge方法
def merge(nums , low , mid , high):
    i = low
    j = mid + 1
    aux = [0 for x in range(high + 1)]
    for k in range(low, high + 1):
        aux[k] = nums[k]
    for k in range(low, high + 1):
        if ( i > mid):
            nums[k] = aux[j]
            j += 1
        elif j > high:
            nums[k] = aux[i]
            i +=1
        elif aux[j] < aux[i]:
            nums[k] = aux[j]
            j += 1
        else:
            nums[k] = aux[i]
            i += 1
  #  return nums
    
# 递归实现
def merge_sort(nums, lo , hi ):
    if(hi <= lo):
        return
    mid = lo +(hi - lo) // 2
    merge_sort(nums , lo , mid)
    merge_sort(nums, mid + 1, hi)
    merge(nums, lo , mid , hi)


# 第一种方法 不借助于栈, 实现自底向上
def merge_sort_1(length, nums):
    aux = [0 for x in range(length)]

    size = 1
    while size < length:
        for lo in range(0, length - size, 2*size):
            merge(nums, lo , lo + size - 1 , min(lo + 2 * size - 1 , length - 1))
        size *= 2
    

if __name__=="__main__":
    for x in sys.stdin:
        tmp = [int(i) for i in x.strip().split(" ")]
        length = tmp[0]
        tmp = tmp[1:]
    #    merge_sort(tmp, 0 , length - 1)
        merge_sort_1(length , tmp)
        ans = ""
        for i in tmp:
            ans += str(i) + " "
        print(ans.strip())