【Day25】[演算法]-合并排序法Merge Sort

合并排序法(Merge Sort)原理是会先将原始资料分割成两个资料列，接着再将两个资料继续分割成两个资料列，依此类推，直到无法再分割，也就是每组都只剩下一笔资料时，再两两合并各组资料，合并时也会进行该组排序，每次排序都是比较最左边的资料，将较小的资料加到新的资料列中，依此类推，直到最後合并成一个排序好的资料列为止。

下面利用30 10 40 70 50 90 60 20由小到大排序。

时间复杂度 = 分割步骤数 + 合并步骤数

分割：分割含有 n 个资料需要 n-1 次，O(n)。
合并：合并的两边共用 n 个元素，每次都是比较最左边的资料，将较小的加到新阵列中，因此每次排序与合并必须经过 n 次，每回合log n次，O(log n)。

平均时间复杂度为: O(n log n)

JavaScript

let data = [8,6,1,10,5,3,9,2,7,4]

function merge(left, right){
  let result = [];

  while (left.length&&right.length){
    //左右两阵列第一个元素进行比较，较小的推入result
    if (left[0] < right[0]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }
  
  //while回圈跳出时，表示左右阵列其中一个为空，因此左右判断concat哪边
  result = left.length ? result.concat(left) : result.concat(right)

  return result;
}

function mergeSort(array){

  if(array.length < 2){
    return array;
  }

  let mid = Math.floor(array.length/2);
  let leftArray = array.slice(0, mid);
  let rightArray = array.slice(mid, array.length);
  
  //用递回一直切到最後一个元素再合并
  return merge(mergeSort(leftArray), mergeSort(rightArray))
}

console.log(mergeSort(data))//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Python

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def merge(left, right):
    result = []

    while len(left) and len(right):
        if (left[0] < right[0]):
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    result = result+left if len(left) else result+right
    return result

def mergeSort(array):
    if len(array) < 2:
        return array

    mid = len(array)//2
    leftArray = array[:mid]
    rightArray = array[mid:]

    return merge(mergeSort(leftArray),mergeSort(rightArray))

print(mergeSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]