神剑山庄资源网 Design By www.hcban.com

归并排序

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

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)

总结

标签:
python归并排序,C语言归并排序,python归并排序算法

神剑山庄资源网 Design By www.hcban.com
神剑山庄资源网 免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
神剑山庄资源网 Design By www.hcban.com

评论“golang/python实现归并排序实例代码”

暂无golang/python实现归并排序实例代码的评论...

《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。