归并排序——如何使用golang和python实现-创新互联

归并排序——如何使用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
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;
}