Just Do IT !

Python算法学习day8:线性时间排序(希尔排序, 计数排序)

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

希尔排序

(1) 希尔排序思路

  • 希尔排序是一种分组插入排序算法。
  • 首先取一个整数d1=n/2, 将元素分为d1个组. 每组相邻量元素之间距离为d1, 在各组内进行直接插入排序;
  • 取第二个整数d2=d1/2, 重复上述分组排序过程, 直到di=1. 即所有元素在同一组内进行直接插入排序

(2) 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def insert_sort_part(li, d): # 分组插入排序实现
	for i in range(d,len(li)):
		tmp = li[i]
		j = i - d
		while j >= 0 and li[j] > tmp:
			li[j+d] = li[j]
			j- = d
		li[j+d] = tmp
		
def shell_sort(li, d):
	d = len(li) // 2
	while d > 0:
		insert_sort_part(li. d)
		d = d // 2

计数排序

(1) 计数排序思路

  • 花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max

  • 开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)

  • 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数

  • 最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数

在这里插入图片描述

(2) 代码实现

1
2
3
4
5
6
7
8
9
def count_sort(li, max):
# max表示列表里的最大值
	count = [0 for i in range(max + 1)]
	for value in li:
		count[value] += 1
	li.clear()
	for i, v in range enumerate(count):
		for k in range(v):
			li.append(i)

缺点: 元素的范围不能太大

原文作者：浩翰

原文链接：https://plutoacharon.github.io/2020/02/23/Python算法学习day8-线性时间排序-希尔排序-计数排序/

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

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

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

CATALOG
  1. 1. 希尔排序
    1. 1.1. (1) 希尔排序思路
    2. 1.2. (2) 代码实现
  2. 2. 计数排序
    1. 2.1. (1) 计数排序思路
    2. 2.2. (2) 代码实现
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