欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

十个必知的排序算法|Python实例系列[1]

程序员文章站 2022-06-15 08:43:41
实例内容: 十个必知的排序算法具体代码,并简略的得知每种算法对于不同长度数列的排序时间 十大排序: 1.冒泡排序2.选择排序3.插入排序4.希尔排序5.归并排序6.快速排序7.堆排序8.计数排序9.桶排序10.基数排序 "代码演示视频" 完整代码和注释如下 ......

实例内容:

十个必知的排序算法具体代码,并简略的得知每种算法对于不同长度数列的排序时间

十大排序:

1.冒泡排序2.选择排序3.插入排序4.希尔排序5.归并排序6.快速排序7.堆排序8.计数排序9.桶排序10.基数排序

代码演示视频

完整代码和注释如下

# -*- coding: utf-8 -*-
#space: https://github.com/tri-x/exercise
#space: https://space.bilibili.com/187492698
#author: trix
#description: 十大经典排序算法

#python的排序算法用的是tim sort 一种源自归并排序和插入排序的稳定高效的排序算法 也许以后会单独做一期视频来介绍该算法
#也许以后会做一期视频来介绍一些奇葩的排序算法 比如 睡眠排序、猴子排序、面条排序、珠排序

from random import randint#随机整数
from time import process_time#计时

nums_lists=[[]for n in range(4)]#随机创建四个无序数列 用来粗略地测试每种排序算法的用时
for n in range(500):#数列长度为500
	nums_lists[0].append(randint(-400,400))#随机范围(-400,400)
for n in range(1000):
	nums_lists[1].append(randint(-8000,8000))
for n in range(5001):
	nums_lists[2].append(randint(-2000,2000))
for n in range(10000):
	nums_lists[3].append(randint(-9000,9000))
#由于创建的随机数列太长,就不打印排序前和排序后的结果了


def bubble_sort(num_list):#冒泡排序 该算法名字的由来是因为越小的值会慢慢"浮"到数列的顶端
	#循环遍历数列,一次比较两个相邻的值,如果后者值大于前者值,就把他们的位置互相交换
	for n in range(len(num_list)-1):#因为最后一次已经顺序正确了所以循环次数-1
		for m in range(len(num_list)-1-n):
			#循环每结束一次 这一次循环中最大的值会移动到上一次循环中最大值的前一位 数列中后面的值已经有序 所以次数-n
			if num_list[m]>num_list[m+1]:#大小比较
				num_list[m+1],num_list[m]=num_list[m],num_list[m+1]#位置交换
	return num_list


def select_sort(num_list):#选择排序 选择最小值
	#每次循环在数列中找到最小值,放到上一次循环找到的最小值的后一位,第一次放在首位
	for n in range(len(num_list)-1):#因为最后一次已经顺序正确了所以循环次数-1
		min_index=n#设最小值为索引为n的值
		for m in range(n,len(num_list)):#n值前已完成排序
			if num_list[m]<num_list[min_index]:#最小值比较
				num_list[min_index],num_list[m]=num_list[m],num_list[min_index]#位置交换
	return num_list


def insert_sort(num_list):#插入排序 插入数值 此版本为插入排序最原始的版本
	#每次循环把索引为1的值到索引为第n次的值作为有序数列,把有序数列以外的每个值插入有序数列的正确位置
	for n in range(1,len(num_list)+1):#从第二个值开始
		for m in range(n):#每个值滚动的范围是其索引值
			if n<len(num_list):#防止n值超出数列长度
				if num_list[n]<=num_list[m]:#比较大小
					num_list[n],num_list[m]=num_list[m],num_list[n]#位置交换
	return num_list


def shell_sort(num_list):#希尔排序 插入排序的改进版 shell的音译
	#把整个无序数列按步长值分组,对每组数列分别进行插入排序,每次结束后减小步长,当步长值减小到1时对整个数列插入排序
	gap=len(num_list)//2#gap为步长值 //为除法向下取值
	while gap>=1:#控制步长范围
		#以下为插入排序的内容 并对插入排序进行了改进
		for n in range(gap,len(num_list)):
			while (n-gap)>=0:#控制比较范围
				if num_list[n]<num_list[n-gap]:#比较相邻两值大小
					num_list[n],num_list[n-gap]=num_list[n-gap],num_list[n]#位置交换
					n-=gap#把比较的两个值的索引向前移
				else:#超出索引范围后结束该循环
					break
		gap//=2#每次结束时减小步长值
	return num_list

def merge_sort(num_list):#归并排序 二分法 递归与合并
	#把无序数列递归地二分,直到只有两个或一个值为一组时,比较值的大小并排序,再返回这一组,
	#再递归地和其它组比较每个值的大小并排序,再返回排序的结果,再递归地返回成有序数列
	if len(num_list)<=1:#限制每组数列的最小长度
		return num_list
	middle=len(num_list)//2#二分值 //表示除法向下取整
	list_before=merge_sort(num_list[:middle])#数列前半部分为list_before 后半部分为list_after
	list_after=merge_sort(num_list[middle:])#这里最好自己举例一个有2或3个值的数列,初次遇见递归思想可能比较难理解
	'''
	比如运行merge_sort([3,2,1])
	[3,2,1]被分成了list_before=merge_sort([3])list_after=merge_sort([2,1])
		list_before=merge_sort([3]):merge_sort函数运行时,因为[3]长度等于1了 所以直接返回[3] 即list_before=[3]
		list_after=merge_sort([2,1]):merge_sort函数运行时,list_after=merge_sort
		在list_after该函数内部又二分成了list_before=merge_sort([2])list_after=merge_sort([1])
			与list_before=merge_sort([3])同理,在list_after该函数内部中,list_before=[2],list_after=[1]
			接着在list_after该函数内部中,执行return merge_compare(list_before,list_after)
			也就是比较[2]和[1]的大小后排序并返回 结果也就是list_after=[1,2]
		再执行return merge_compare(list_before,list_after)也就是比较[3]和[1,2]大小后排序并返回
		结果也就是return [1,2,3]
	最后返回总列表 其它数列以此类推
	'''
	return merge_compare(list_before,list_after)#返回list_before,list_after比较的结果

def merge_compare(list_before,list_after):#比较两个列表中的每个值
	result_list=[]#结果列表
	before_index=after_index=0#前列表和后列表数值的索引起始值
	while before_index<len(list_before) and after_index<len(list_after):#限制索引值
		if list_before[before_index]<list_after[after_index]:#如果前列表的值小于后列表的值
			result_list.append(list_before[before_index])#就把该值添加到结果列表
			before_index+=1#结束后索引值+1
		elif list_after[after_index]<=list_before[before_index]:#如果后列表的值小于等于前列表的值
			result_list.append(list_after[after_index])#同理
			after_index+=1
	if before_index==len(list_before):#如果前列表的索引值已经等于前列表长度了
		for n in list_after[after_index:]:#说明后列表的所有值大于前列表的最大值
			result_list.append(n)#因为后列表在递归中已经完成排序了 直接追加后列表
	elif after_index==len(list_after):#如果后列表的索引值已经等于后列表长度了
		for n in list_before[before_index:]:#同理
			result_list.append(n)
	return result_list#返回排序结果


def quick_sort(num_list):#调用快速排序的递归函数
	quick_recursion(num_list,0,len(num_list)-1)#传入数列,头索引值和尾索引值

def quick_recursion(num_list,head_index,tail_index):#快速排序 递归思想 建议和归并排序一样举例理解
	#从数列中任意挑选一个值(该值称为基准-pivot),设置一个头索引值和尾索引值,用来限定扫描范围,头索引值向尾索引值移动
	#扫描每个值把所有小于基准值的数移到其前,所有大于基准的数移到其后(该步骤称为分区-partition),再在每个分区里递归以上步骤
	if head_index<tail_index:#限制索引值
		pivot_index=quick_partition(num_list,head_index,tail_index)#获取基准所在索引值 这一步同时也完成了分区
		quick_recursion(num_list,head_index,pivot_index-1)#分别在前后分区范围内进行快速排序 因为基准值处于前分区结尾和后分区开头
		quick_recursion(num_list,pivot_index+1,tail_index)#所以对于前分区的尾索引值-1 对于后分区的头索引值+1
	return num_list

def quick_partition(num_list,head_index,tail_index):#比较大小并进行分区
	pivot=num_list[tail_index]#为了方便 选取该分区的结尾值作为基准-pivot
	exchange_index=head_index-1#设置交换索引值 头索引值-1能把几种情况整合成一句代码
	for n in range(head_index,tail_index):#在两个索引值范围内 用基准值来区分每个值
		if num_list[n]<pivot:#如果扫描值小于基准值
			exchange_index+=1#控制交换索引值
			num_list[exchange_index],num_list[n]=num_list[n],num_list[exchange_index]#交换位置
	num_list[exchange_index+1],num_list[tail_index]=num_list[tail_index],num_list[exchange_index+1]#注意有个exchange_index+1
	'''
	比如quick_sort([1,4,5,6,3,4],0,5)
		在[1,4,5,6,3,4]中第一次分区时基准值=4,exchange_index=-1
			n=0时,扫描值1<基准值,exchange_index+1=0,再执行for循环时的下一行的交换位置的代码 等效于扫描值1的位置不变
			n=1时,扫描值4=基准值,exchange_index不变,exchange_index仍为0
			n=2时,扫描值5>基准值,exchange_index不变,exchange_index仍为0
			n=3时,扫描值6>基准值,exchange_index不变,exchange_index仍为0
			n=4时,扫描值3<基准值,exchange_index+1=1,再执行for循环时的下一行的交换位置的代码 等效于扫描值4和扫描值3交换位置
		此时for循环结束,执行for循环结束后的的下一行交换位置的代码 等效于扫描值5和基准值4交换位置
		第一次分区结束后我们得到了[1,3,4,6,4,5] partition函数返回了pivot_index=2
	接着在quick_sort函数内部继续运行quick_sort([1,3,4,6,4,5],0,2-1)和quick_sort([1,3,4,6,4,5],2+1,5)
	即对于[1,3]和[6,4,5]进行partition函数,同理 不赘述
	对于整个数列递归partition结束后 排序也就完成 其它数列以此类推
	'''
	return exchange_index+1#返回基准值所在的索引值


def heap_sort(num_list):#堆排序 完全二叉树 递归
	#递归地把数列形成每个父节点>每个左右子节点的完全二叉树
	#这样每次构建后索引[0]为最大值,在第n次结束,就把[0]和[-n]位置互换 在[0:-n-1]的范围内进行下次的完全二叉树构建
	list_len=len(num_list)#获取数列长度
	for n in range(list_len//2,-1,-1):
	#list_len//2为父节点索引的规律 //表示除法向下取整 n∈[list_len//2,-1),n∈z range(start,stop,step) step为-1时为从后往前遍历
		heapify(num_list,list_len,n)#数列完全二叉树的初始化 构建每个父节点>每个左右子节点的完全二叉树
	for n in range(list_len-1,0,-1):#n∈[list_len-1,0),n∈z
		num_list[0],num_list[n]=num_list[n],num_list[0]#对上一次构建完成的二叉树 首尾值互换
		list_len-=1#限定这一次构造完全二叉树的范围
		heapify(num_list,list_len,0)#由于已经初始化完成 可以直接从首项开始 在不包含上次最大值的范围内进行构造完全二叉树
	return num_list

def heapify(num_list,list_len,parent_index):#构建父节点>左右子节点的完全二叉树
	#第n排有n^(n-1),从左到右填充数值,可以得到父节点索引和左右子节点索引的规律
	left_index=2*parent_index+1#对于每个父节点索引 左节点索引的规律
	right_index=left_index+1#对于每个父节点索引 右节点索引的规律
	max_index=parent_index#假设父节点比左右子节点值都大 默认最大值的索引为父节点索引
	if left_index<list_len and num_list[left_index]>num_list[max_index]:#如果在列表范围内 左节点值>父节点值
		max_index=left_index#父节点和左节点的索引互换
	if right_index<list_len and num_list[right_index]>num_list[max_index]:#右节点同理
		max_index=right_index
	if max_index!=parent_index:#如果现在的父节点索引不等于一开始的假设的最大值的索引 说明父节点和它的某一节点需要互换索引值
		num_list[parent_index],num_list[max_index]=num_list[max_index],num_list[parent_index]
		heapify(num_list,list_len,max_index)#递归构建整个数列的完全二叉树


def count_sort(num_list):#计数排序 数数
	#找出数列中最大值和最小值 创建min~max这么多个0用来统计数列中每个值出现的次数,再从最小值依次排放到最大值
	max_num=max(num_list)#找到最大值
	min_num=min(num_list)#找到最小值
	neg_list=[]#负数数列
	pos_list=[]#非负数数列
	for num in num_list:#对负数和非负数分别处理
		if num<0:
			neg_list.append(num)#向负数数列添加负数
		if num>=0:
			pos_list.append(num)#向非负数数列添加非负数
	if len(neg_list)!=0:#如果有负数
		neg_counts_list=[0 for n in range(min_num,0)]#创建最小值这么多个0来累计每个负数出现的次数
		for n in range(len(neg_list)):#对于负数数列中的每个值
			neg_counts_list[neg_list[n]]+=1
		neg_index=0#初始排序索引为0
		for n in range(-len(neg_counts_list),0):#对于计数列表中的每一项
			while neg_counts_list[n]>0:#不为0就说明有计数 为0说明没有计数
				neg_list[neg_index]=n#依次排放数值
				neg_index+=1#每次排放后index+1
				neg_counts_list[n]-=1#每次排放后数值所对应的计数-1
	if len(pos_list)!=0:#如果有非负数
		pos_counts_list=[0 for n in range(max_num+1)]#创建max+1这么多个0来累计每个非负数出现的次数 因为是以每个值为索引 所以要max+1个0
		for n in range(len(pos_list)):#对于数列中的每个非负值
			pos_counts_list[pos_list[n]]+=1#计数列表索引和数列的值一一对应
		pos_index=0#初始排序索引为0
		for n in range(len(pos_counts_list)):#对于计数列表中的每一项
			while pos_counts_list[n]>0:#不为0就说明有计数 为0说明没有计数
				pos_list[pos_index]=n#依次排放数值
				pos_index+=1#每次排放后index+1
				pos_counts_list[n]-=1#每次排放后数值所对应的计数-1
	result_list=neg_list+pos_list#负数数列和非负数数列结合
	return result_list


def bucket_sort(num_list):#桶排序 计数排序的改进版
	#找出数列中最大值和最小值 创建min~max这么多个桶用来统计数列中每个值出现的次数,再从第一个桶倾倒到最后一个桶
	bucket_list=[0 for n in range(max(num_list)-min(num_list)+1)]#创建min~max这么多个桶
	for n in range(len(num_list)):#对于当前值
		bucket_list[num_list[n]-min(num_list)]+=1#添加到值对应的桶内 即对应桶计数+1
	result_list=[]#结果列表
	for n in range(len(bucket_list)):#对于每个桶
		if bucket_list[n]!=0:#如果桶内有数
			result_list+=[n+min(num_list)]*bucket_list[n]#直接把桶里的所有数倒出来
	return result_list


def radix_sort(num_list):#基数排序 比较位数上的值
	#比较每一位上的数字大小 当每一位比较完成排序也就完成
	pos_list=[]#负数数列
	neg_list=[]#非负数数列
	for num in num_list:#对负数和非负数分别处理
		if num<0:
			neg_list.append(num)
		if num>=0:
			pos_list.append(num)

	if len(neg_list)!=0:#如果有负数
		neg_num_digit=0#初始位数
		while neg_num_digit<len(str(min(neg_list))):#限制条件 当数的位数小于最小值位数时
			neg_values_lists=[[] for n in range(10)]#初始化数值列表 每位出现的值只可能是0~9 所以创建10个数值列表
			for neg_num in neg_list:#对于数列中的每个数
				neg_values_lists[int(neg_num/(10**neg_num_digit))%10].append(neg_num)
				#在第neg_num_digit+1次循环就比较该数的第n位上的数值 把该数添加到对应的数值列表 比如第一次循环就比较个位 第二次比较十位
			neg_list.clear()#清空原数列用来填充有序的数列
			for neg_value_list in neg_values_lists:#对于数值列表中的每个列表
				for neg_num in neg_value_list:#对于每个列表中的每个数
					neg_list.append(neg_num)
			neg_num_digit+=1#比较下一位

	if len(pos_list)!=0:#如果有非负数
		pos_num_digit=0#初始位数
		while pos_num_digit<len(str(max(pos_list))):#限制条件 当数的位数小于最大值位数时
			pos_values_lists=[[] for n in range(10)]#初始化数值列表 每位出现的值只可能是0~9 所以创建10个数值列表
			for pos_num in pos_list:#对于数列中的每个数
				pos_values_lists[int(pos_num/(10**pos_num_digit))%10].append(pos_num)
				#在第pos_num_digit+1次循环就比较该数的第n位上的数值 把该数添加到对应的数值列表比如第一次循环就比较个位 第二次比较十位
			pos_list.clear()#清空原数列用来填充有序的数列
			for pos_value_list in pos_values_lists:#对于数值列表中的每个列表
				for pos_num in pos_value_list:#对于每个列表中的每个数
					pos_list.append(pos_num)
			pos_num_digit+=1#比较下一位
	result_list=neg_list+pos_list#结果列表
	return result_list


#记录每一种排序算法对于不同长度无序数列的排序时间
sorts_time_dict={
			bubble_sort:['bubble sort'],#冒泡排序
			select_sort:['select sort'],#选择排序
			insert_sort:['insert sort'],#插入排序
			shell_sort:['shell sort'],#希尔排序
			merge_sort:['merge sort'],#归并排序
			quick_sort:['quick sort'],#快速排序
			heap_sort:['heap sort'],#堆排序
			count_sort:['count sort'],#计数排序
			bucket_sort:['bucket sort'],#桶排序
			radix_sort:['radix sort'],#基数排序
}


for num_list in nums_lists:#由于两层for循环会使对数列进行快速排序时的递归太深 会引起python崩溃 单独对每个数列进行快速排序
	print('正在对第'+str(nums_lists.index(num_list)+1)+'个'+'长为'+str(len(num_list))+'的随机数列执行quick sort算法')
	start_time=process_time()#开始计时 计时部分为排序算法
	quick_sort(num_list)
	end_time=process_time()#结束计时
	sorts_time_dict[quick_sort].append(end_time-start_time)#记录每种排序算法对不同长度数列的排序时间 单位为秒
for num_list in nums_lists:#对每个数列进行每一种排序算法
	for func_sort,time_list in sorts_time_dict.items():
		if func_sort!=quick_sort:
			print('正在对第'+str(nums_lists.index(num_list)+1)+'个'+'长为'+str(len(num_list))+'的随机数列执行'+time_list[0]+'算法')
			start_time=process_time()#开始计时 计时部分为排序算法
			func_sort(num_list.copy())#排序算法 .copy() 复制品 防止改变原数列
			end_time=process_time()#结束计时
			time_list.append(end_time-start_time)#记录每种排序算法对不同长度数列的排序时间 单位为秒
print()
print('十种排序算法对于不同长度的随机无序数列的排序时间结果如下:')
print('{:20s}{:<15d}{:<15d}{:<15d}{:<15d}'.format('length of series:',500,1000,5001,10000))#格式化输出
for time_list in sorts_time_dict.values():#每种算法
	for sort_time in time_list:#每种算法的名称和其处理每个数列的时间
		if not isinstance(sort_time,float):#如果use_time类型不为float 即为名称
			print('{:20s}'.format(sort_time+':'),end='')
		else:
			print('{:<15.4f}'.format(sort_time),end='')#左对齐 保留四位小数
	print()
print('单次随机数列排序时间结果不代表所有')
print()

count_sort_list=[]#因为计数排序太快了,单独创建一个长度为100000的数列来测试排序时间
for n in range(100000):
	count_sort_list.append(randint(-80000,100000))
start_time_count_sort=process_time()#开始计时 计时部分为排序算法
count_sort(count_sort_list.copy())
end_time_count_sort=process_time()#结束计时
print('计数排序一个长度为100000的随机数列所用时间为'+str(round(end_time_count_sort-start_time_count_sort,3))+'秒')