Just Do IT !

Python算法学习day7:归并排序

Python算法
字数统计: 343阅读时长: 1 min
2020/02/23 Share

归并排序

1. 一次归并

在这里插入图片描述
假设现在的列表分两段有序, 如何将其合成为一个有序列表
在这里插入图片描述
选取两段列表,分成两段,然后一一比较
在这里插入图片描述
在这里插入图片描述
比较完成,这便是一次归并

2. 一次归并算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def merge(li, low, mid, high):
	i = low
	j = mid + 1
	li_tmp = []
	while i <= mid and j <= high:
		if li[i] <= li[j]:
			li_tmp.append(li[i])
			i += 1
		if li[i] >= li[j]:
			li_tmp.append(li[j])
			j += 1
	while i <= mid:
		li_tmp.append(li[i])
		i += 1
	while j <= high:
		li_tmp.append(li[j])
		j += 1
	for i in range(low, high+1):
		li[i] = li_tmp[i-low]

例题:已知两个有序列表，实现将这两个列表合并排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def merge_sort(li1, li2):
	i = 0
	j = 0
	li = []
	while i < len(li1) and j < len(li2):
		if li[i] >= li[j]:
			li.append(li[j])
			j += 1
		else:
			li.append(li[i])
			i += 1
	while i < len(li1):
		li.append(li[i])
		i += 1
	while j < len(li2):
		li.append(li[j])
		j += 1

归并排序算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def merge_sort(li, low, high):
	if low < high:
		mid = (low + high) // 2 
		merge_sort(li, low , mid)
		merge_sort(li, mid + 1, high)
		merge(li, low, mid, high)
		
def merge(li, low, mid, high):
	i = low
	j = mid + 1
	li_tmp = []
	while i <= mid and j <= high:
		if li[i] <= li[j]:
			li_tmp.append(li[i])
			i += 1
		if li[i] >= li[j]:
			li_tmp.append(li[j])
			j += 1
	while i <= mid:
		li_tmp.append(li[i])
		i += 1
	while j <= high:
		li_tmp.append(li[j])
		j += 1
	for i in range(low, high+1):
		li[i] = li_tmp[i-low]

原文作者：浩翰

原文链接：https://plutoacharon.github.io/2020/02/23/Python算法学习day7-归并排序/

发表日期：February 23rd 2020, 8:22:40 pm

更新日期：February 23rd 2020, 8:23:22 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 归并排序
    1. 1.1. 1. 一次归并
    2. 1.2. 2. 一次归并算法实现
    3. 1.3. 例题:已知两个有序列表，实现将这两个列表合并排序
    4. 1.4. 归并排序算法实现
Total : 190
2020
2019
CTF Liunx 高可用负载均衡 Java Hadoop Docker Esxi Dokcer Flume GitHub Kafka Golang Golang日志收集系统 Hbase Hive Git Kali Kubernetes Shell Python算法 Spark Sqoop Vmware 机器学习 Zookeeper PHP Hexo 安全 Python PySpark Maven 网络 数据采集 CDN AWD ZooKeeper
CTF Liunx Hadoop Docker GitHub Golang Golang日志收集系统 高可用负载均衡 Hive Java Kubernetes 其他 Python算法 Spark Vmware 机器学习 博客 Python 网络 CDN