归并排序详解(python实现)
2024-08-25 01:35:34
因为上个星期leetcode的一道题(Median of Two Sorted Arrays)所以想仔细了解一下归并排序的实现。
还是先阐述一下排序思路:
首先归并排序使用了二分法,归根到底的思想还是分而治之。拿到一个长数组,将其不停的分为左边和右边两份,然后以此递归分下去。然后再将她们按照两个有序数组的样子合并起来。这样说起来可能很难理解,于是给出一张我画的图。
这里显示了归并排序的第一步,将数组按照middle进行递归拆分,最后分到最细之后再将其使用对两个有序数组进行排序的方法对其进行排序。
两个有序数组排序的方法则非常简单,同时对两个数组的第一个位置进行比大小,将小的放入一个空数组,然后被放入空数组的那个位置的指针往后 移一个,然后继续和另外一个数组的上一个位置进行比较,以此类推。到最后任何一个数组先出栈完,就将另外i一个数组里的所有元素追加到新数组后面。
由于递归拆分的时间复杂度是logN 然而,进行两个有序数组排序的方法复杂度是N该算法的时间复杂度是N*logN 所以是NlogN。
根据这波分析,我们可以看看对上图的一个行为。
当最左边的分到最细之后无法再划分左右然后开始进行合并。
第一次组合完成[4, 7]的合并
第二次组合完成[4, 7, 8]的合并
第三次组合完成[3, 5]的合并
第四次组合完成[3, 5, 9]的合并
第五次组合完成[3, 4, 5, 7, 8, 9]的合并结束排序。
下面放上python的代码
def merge(a, b):
c = []
h = j = 0
while j < len(a) and h < len(b):
if a[j] < b[h]:
c.append(a[j])
j += 1
else:
c.append(b[h])
h += 1 if j == len(a):
for i in b[h:]:
c.append(i)
else:
for i in a[j:]:
c.append(i) return c def merge_sort(lists):
if len(lists) <= 1:
return lists
middle = len(lists)/2
left = merge_sort(lists[:middle])
right = merge_sort(lists[middle:])
return merge(left, right) if __name__ == '__main__':
a = [4, 7, 8, 3, 5, 9]
print merge_sort(a)
Java 实现
package com.geektime.SortQ; import java.util.ArrayList;
import java.util.Arrays;
import java.util.List; public class MergeSort { public void merge(List<Integer> arrays, List<Integer> pp, List<Integer> gg, int start, int end) {
int pIndex = 0;
int gIndex = 0;
ArrayList<Integer> temp = new ArrayList<Integer>();
while (true) {
if (pp.get(pIndex) >= gg.get(gIndex)) {
temp.add(gg.get(gIndex));
gIndex++;
} else {
temp.add(pp.get(pIndex));
pIndex++;
}
if (gIndex == gg.size()) {
for (int i = pIndex; i < pp.size(); i++)
temp.add(pp.get(i));
break;
} else if (pIndex == pp.size()) {
for (int j = gIndex; j < gg.size(); j++)
temp.add(gg.get(j));
break;
}
} for (int op = 0; op < temp.size(); op++) {
arrays.set(start+op, temp.get(op));
}
} public void mergeSort(ArrayList<Integer> arrays, int start, int end) {
if (start >= end)
return;
int mid = (start + end) / 2; mergeSort(arrays, start, mid);
mergeSort(arrays, mid+1, end);
List<Integer> pp = arrays.subList(start, mid+1);
List<Integer> gg = arrays.subList(mid+1, end+1);
merge(arrays, pp, gg, start, end);
} public static void main(String[] args) {
MergeSort bb = new MergeSort();
ArrayList<Integer> arrayList = new ArrayList<Integer>(Arrays.asList(4, 5, 6, 3, 2, 1));
bb.mergeSort(arrayList,0, 5);
System.out.println(arrayList);
}
}
最新文章
- ionic day01教程第一天之多平台运行(ios & android)
- java操作Redis
- 使用";关键词";来整理自己的知识库
- JavaScript与java的异同(一)
- 整合Spring Data JPA与Spring MVC: 分页和排序
- ssh框架整合---- spring 4.0 + struts 2.3.16 + maven ss整合超简单实例
- (转)CSS 为不同大小的浏览器视窗使用不同的样式表
- Oracle基础 游标
- 递归小Demo
- android slidingview
- NLP 苏图南 打破自我设限 突破自我—在线播放—优酷网,视频高清在线观看
- DaTaX当成jar包当作第三方库启动的相关问题
- Unity脚本自动添加注释脚本及排版格式
- B. Switches and Lamps
- Nginx反向代理后端多节点下故障节点的排除思路
- 为什么QQ空间和QQ邮箱都是IE默认打开?
- centos 6.3 64位下cpuminer +mining_proxy 挖掘莱特币(LTC)教程
- Spring AOP源码分析(二)动态A0P自定义标签
- Flask wtform组件
- Flex 布局的各属性取值解释
热门文章
- Linux监控命令整理(top,free,vmstat,iostat,mpstat,sar,netstat)
- Linux安装solr
- spring+springmvc+hibernate整合实例
- Qt中 .pro 文件和 .pri 文件简介
- Linux kernel Programming - Allocating Memory
- UOJ14 DZY Loves Graph 并查集
- LiveCharts文档-1前言
- 面试3——java集合类总结(List)
- python第二周
- maven docker 插件集成的几个小坑