golang/python实现归并排序实例代码

归并排序

思路：将数组不断二分，然后合并为有序数组

C++实现:

void mergeSort(T arr[], int left,int right) { //对arr[left,right]的范围进行排序
if (left >= right)
 return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right); //合并两部分
}

template<typename T>
void __merge(T arr[], int left, int mid, int right) { //将arr[left,mid] 和 arr[mid+1,right] 两部分进行归并

T *tmp=new T[right-left+1];
for (int i = left; i <= right; i++)
 tmp[i - left] = arr[i]; //先把arr（需要合并的左右片段） 复制给tmp

int i = left, j = mid + 1; // i 做为左半部分的指针 j作为右半部分的指针
for (int k = left; k <= right; k++) {
 if (i > mid) { // 左半部分 已经合入完了，将右半部分剩下的 全部合入
  arr[k] = tmp[j - left];
  j++;
 }
 else if (j > right) { // 右半部分 已经合入完了，将左半部分剩下的 全部合入
  arr[k] = tmp[i - left];
  i++;
 }
 else if (tmp[i - left] < tmp[j - left]) {
  arr[k] = tmp[i - left];
  i++;
 }
 else {
  arr[k] = tmp[j - left];
  j++;
 }
}
delete[] tmp;
}

GoLang实现:

func mergeSort(arr []int, left, right int) {
if left >= right {
 return
}
mid := left + (right-left)/2
mergeSort(arr, left, mid) // 递归调用，分别对左右部分进行归并排序
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right) // 将左右部分进行合并
}

func merge(arr []int, left, mid, right int) {
// 将要合并的部分做个拷贝
var tmp []int = make([]int, right-left+1)
for i, j := left, 0; i <= right; i++ {
 tmp[j] = arr[i]
 j++
}
// i做为左半部分的指针 j作为右半部分的指针
var i, j int = left, mid+1
for k := left; k <= right; k++ {
 if i > mid { // 左半部分 已经合入完了，将右半部分剩下的 全部合入
  arr[k] = tmp[j-left]
  j++
 } else if j > right { // 右半部分 已经合入完了，将左半部分剩下的 全部合入
  arr[k] = tmp[i-left]
  i++
 } else if tmp[i-left] > tmp[j-left] {
  arr[k] = tmp[j-left]
  j++
 } else {
  arr[k] = tmp[i-left]
  i++
 }
}
}

python实现:

python 的实现方法和上面不一样，上面两种方法都是在原始数组上直接进行修改的

def mergeSort(arr):
if len(arr) <= 1:
 return arr
mid = len(arr) // 2
left = mergeSort(arr[:mid]) # 分别对左右部分排序
right = mergeSort(arr[mid:])
return merge(left, right) # 合并左右部分为有序数组

def merge(left, right):
result = []
num_left, num_right = left.pop(0), right.pop(0) # 分别取出左右部分的第0个元素
while True:
 if num_left < num_right:
  result.append(num_left)
  try:
   num_left = left.pop(0)
  except IndexError:
   result.append(num_right)
   result.extend(right)
   break
 else:
  result.append(num_right)
  try:
   num_right = right.pop(0)
  except IndexError:
   result.append(num_left)
   result.extend(left)
   break
return result

if __name__ == '__main__':
from random import shuffle

arr = list(range(30))
shuffle(arr)
arr = mergeSort(arr)
print(arr)

来源：https://www.jianshu.com/p/0abb8b4045e1