golang/python实现归并排序实例代码
作者:NothingLeft了 时间:2023-12-13 04:19:01
归并排序
思路:将数组不断二分,然后合并为有序数组
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
标签:golang,python,归并排序
0
投稿
猜你喜欢
pycharm安装图文教程
2022-01-14 08:43:42
python 3调用百度OCR API实现剪贴板文字识别
2022-12-13 19:01:14
python 实现矩阵按对角线打印
2022-08-01 02:01:07
python实现LBP方法提取图像纹理特征实现分类的步骤
2023-05-24 02:12:27
跟老齐学Python之有容乃大的list(1)
2021-08-17 00:27:09
Python实现连接两个无规则列表后删除重复元素并升序排序的方法
2021-05-23 10:35:54
Python机器学习库scikit-learn入门开发示例
2022-10-15 11:40:24
Python 实现局域网远程屏幕截图案例
2021-05-13 13:43:43
一个拖动层和Onmouse自动下拉效果
2007-10-08 21:25:00
在脚本中单独使用django的ORM模型详解
2021-03-09 05:17:26
python 动态绘制爱心的示例
2022-10-22 08:20:23
Oracle数据库密码文件的使用与维护
2010-07-28 13:27:00
Python使用Redis实现作业调度系统(超简单)
2023-04-22 03:57:59
基于Python实现智能停车场车牌识别计费系统
2021-05-23 07:44:22
Python实现自动化处理Word文档的方法详解
2022-05-24 00:33:59
ASP中使用SQL语句教程
2008-09-03 12:17:00
python使用super()出现错误解决办法
2021-05-01 02:48:48
XHTML中用途相似的标签
2008-03-24 19:33:00
Python中转换角度为弧度的radians()方法
2021-08-11 16:21:59
Python tkinter布局与按钮间距设置方式
2023-09-28 23:43:27