python基础教程golang/python实现归并排序实例代码

ゞ浴缸里的玫瑰 2022-12-19 09:29 105阅读 0赞

更多教程请到：菜鸟教程https://www.piaodoo.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)

**总结**

到此这篇关于golang/python实现归并排序的文章就介绍到这了,更多相关golang python归并排序内容请搜索菜鸟教程www.piaodoo.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持菜鸟教程www.piaodoo.com！