tqlovepy

用户名：uq_91509931799

访问量：1976

签　名：

编程是爱好，数学是推动爱好前进的好帮手

等　　级
排　　名	2464
经　　验	2307
参赛次数	4
文章发表	3
年　　龄	21
在职情况	学生
学　　校	淮北师范大学
专　　业	光电信息科学与工程

　　自我简介：

爱做题爱python

TA的其他文章

dp保姆级题解（python+ c语言+ c++三种语言实现 + 代码图解）
浏览：1185

八种排序算法（python实现）
浏览：493

你可能喜欢

八种排序算法（python实现）

　　作者: tqlovepy　　　　发表时间：2022-02-03 11:07:10 浏览：493　|　评论：0　

原题链接：排序

"""
以下是八种升序排序算法模板
分为初级排序算法和高级排序算法
初级排序算法：插入排序，选择排序，冒泡排序
高级排序算法：归并排序，快速排序，希尔排序，堆排序，桶排序

时间复杂度：
O(n^2):插入、选择、冒泡
O(n^1.3 ~ n^2):希尔
O(nlgn):归并、快速、堆
O(n):桶

稳定与否：
稳定：插入、冒泡、归并、桶
不稳定：选择、快速、希尔、堆

使用递归：快速、归并

数据量较小时：使用插入、选择、冒泡、希尔(编写代码短，省时省力)
数据量较大时：使用归并、快速、堆(时间复杂度较低)
数据元素为整形时：可使用桶，但要考虑数据量的范围，如果范围过大，则需要申请很多的空间
一般情况下都是用语言封装好的sort函数，一般都为快速排序
"""

```python
def insert_sort(a):                     
#插入排序，a为待排序数组
	for i in range(1,len(a)):           
	#遍历未排序的元素
		for j in range(i):              
		#遍历已排序的元素
			if a[i] < a[j]:	         
			#找到插入位置
				ins = a.pop(i)          
				#取出要插入的元素
				a.insert(j,ins)         
				#插入元素
				break                   
				#插入后跳出“遍历已排序数组”的循环
	return a                            
	#返回已排序数组
```

```python
def shell_sort(a):                                          
#希尔排序(缩小增量排序)，a为待排序数组
	step = len(a) // 2 										
	#初始化增量为数组长度的一半
	while step > 0:											
	#增量必须是大于0的整数
		for i in range(step,len(a)):						
		#遍历需要进行插入排序的数
			idx = i 										
			#将遍历到的数的下标存放到idx中
			while idx >= step and a[idx] < a[idx - step]:	
			#当下标大于等于增量且后者小于前者时
				a[idx],a[idx - step] = a[idx - step],a[idx]	
				#交换前后两者
				idx -= step									
				#将下标减去增量值，因为交换后的数与前面的数还要进行判定大小和和交换
		step //= 2  										
		#增量缩小一半
	return a 												
	#返回已排序数组
```

```python
def select_sort(a):                                   
#选择排序（优化版），a为待排序数组
	for i in range(len(a)-1):							
	#遍历未排序元素								 								 
		minidx = i   								 	
		#最小值索引存放当前遍历的元素索引
		for j in range(i+1,len(a)):						
		#遍历当前元素之后的元素
			if a[j] < a[minidx]:								
			#如果发现有小于当前值的元素
				minidx = j								
				#就更新最小值索引为当前值索引
		if minidx != i:									
		#遍历结束，如果最小值索引不等于初始值
			a[minidx],a[i] = a[i],a[minidx]				
			#就交换最小值和无序数组中的第一个元素
	return a   											
	#返回已排序数组
```

```python
def bubble_sort(a):                            
#冒泡排序，a为待排序数组
	n = len(a)									
	#求数组元素个数
	for i in range(n-1):						
	#n个元素进行n-1次比较
		flag = 0  								
		#flag用于比较是否有元素交换发生
		for j in range(n-1-i):					
		#遍历未排序的数组
			if a[j] > a[j + 1]:					
			#如果前者大于后者
				a[j],a[j + 1] = a[j + 1],a[j]	
				#就交换
				flag = 1  						
				#同时flag置1，表示发生了元素交换
		if not flag:							
		#如果没有元素交换，说明数组已经排好序了
			break								
			#就跳出循环
	return a   									
	#返回已排序数组
```

```python
def merge_sort(a):                                             
#归并排序，a为待排序数组
	n = len(a)													
	#求数组元素个数
	if n <= 1:													
	#如果只有一个元素（递归边界条件）
		return a 												
		#则返回这个只有一个元素的数组
	mid = n // 2                                                
	#求出数组的中位数
	llist,rlist = merge_sort(a[:mid]),merge_sort(a[mid:])       
	#递归调用函数分别为左右数组排序
	result = []                                                
	#用来存放已排序元素
	i = j = 0                                                  
	#i，j分别记录左子数组和右子数组等待加入元素的位置
	while i < len(llist) and j < len(rlist):					
	#合并两个有序数组
		if rlist[j] < llist[i]:									
		#如果右子数组的当前值小于左子数组的当前值
			result.append(rlist[j])                            
			#就将右子数组的当前值添加到result数组的末尾
			j += 1                                             
			#右子数组的当前值右移
		else:                                                  
		#如果右子数组的当前值大于等于左子数组的当前值
			result.append(llist[i])                            
			#就将左子数组的当前值添加到result数组的末尾
			i += 1                                             
			#左子数组的当前值右移
	result += llist[i:] + rlist[j:]                           
	#把数组未添加的部分加到结果数组末尾
	return result                                             
	#返回已排序数组
```

```python
def quick_sort(a,left,right):              
#快速排序（改进版），子数组的第一个元素和最后一个元素在数组中的位置
	if left >= right:						
	#如果左指针指向的位置在右指针指向的位置的右边或者重合
		return 								
		#就返回
	l,r,key = left,right,a[left]           
	#初始化左指针，右指针和基准值
	while l < r:							
	#调整元素位置
		while l < r and a[r] > key:  		
		#当右指针指向的值大于基准值
			r -= 1							
			#右指针左移
		a[l] = a[r]                        
		#当右指针指向的值小于基准值结束循环后，将右指针指向的值由左指针指向
		while l < r and a[l] < key:			
		#当左指针指向的值小于基准值
			l += 1   						
			#左指针右移
		a[r] = a[l] 						
		#当左指针指向的值大于基准值结束循环后，将左指针指向的值由右指针指向
	a[l] = key								
	#把基准值赋给左指针和右指针共同指向的位置
	quick_sort2(a,left,l-1)					
	#左侧数组快排
	quick_sort2(a,l+1,right)  				
	#右侧数组快排
	return a				     			
	#返回已排序数
```

```python
def heapify(a,start,end):		
#堆化(向下调整)函数,start为堆顶节点的编号，end为堆末尾的界限值
	father = start									
	#father存放堆顶节点				
	son = father * 2 								
	#son存放较大的子节点的编号，初始化为左子节点
	while son <= end:								
	#父节点还有子节点时，继续循环调整
		if son + 1 <= end and a[son + 1] > a[son]:	
		#如果存在右子节点且其值大于左子节点的值
			son += 1 								
			#son存放右子节点的编号
		if a[father] < a[son]:						
		#如果父亲节点的值小于子节点中的最大值时
			a[father],a[son] = a[son],a[father]		
			#交换父亲节点和子节点
			father = son							
			#父亲节点下移到他的子节点
			son = father * 2 						
			#son更新为“更新后的父亲节点的左子节点的编号”，进入下一层调整
		else:										
		#如果父亲节点大于子节点，说明该节点的子堆已调整完成
			return									
			#函数返回调用处

def heap_init(a):							
#初始化大顶堆的函数
	a.insert(0,0)							
	#堆顶编号从1开始，在位置0处插入一个数使得堆中元素的编号与在数组中的下标一样
	for i in range((len(a)-1)//2,0,-1):     
	#从最底层最右侧的非叶子节点开始调整
		heapify(a,i,len(a)-1) 				
		#调用堆化函数

def heap_sort(a):							
#堆排序，a为待排序数组
	for i in range(len(a)-1,0,-1):			
	#从堆末尾开始进行元素交换
		a[1],a[i] = a[i],a[1]				
		#将堆顶元素和堆末尾元素进行交换
		heapify(a,1,i-1)					
		#交换后调用堆化函数调整堆顶元素变为最大值，i-1表示删去交换后的末尾元素
```

```python
def barrel_sort(a):									
#桶排序，a为待排序数组
	minval,maxval = min(a),max(a)					
	#找出数组中的最大值和最小值
	count = [0] * (maxval - minval + 1)				
	#设置一个长度为maxval-minval+1桶
	ans = []										
	#存放排好序的数组
	for i in a:										
	#遍历待排序数组
		count[i - minval] += 1 						
		#统计每个元素出现的次数，桶的编号与对应元素不一致
	for i in range(len(count)):						
	#遍历桶
		if count[i]:								
		#如果桶内有元素
			ans += [i + minval] * count[i]			
			#往结果数组中加上相应数量的元素
	return ans										#返回排好序的数组
```

注意：所有代码为排序模板代码，而非题解代码，题解有多组数据，所以要判断是否到了文件尾部
python判断是否到文件尾的代码格式如下：
```python
try:
	while 1:
		#此处写核心代码
except EOFError:pass
```

0.0分

5 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

tqlovepy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

【计算直线的交点数】（C语言代码）

C二级辅导-同因查找（C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

八种排序算法（python实现）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

不容易系列（C语言代码）

简单的a+b （C++语言代码）

拆分位数（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

C语言考试练习题_一元二次方程（C语言代码）

tqlovepy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

【计算直线的交点数】 （C语言代码）

C二级辅导-同因查找 （C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

八种排序算法（python实现）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

不容易系列 （C语言代码）

简单的a+b （C++语言代码）

拆分位数 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

C语言考试练习题_一元二次方程 （C语言代码）

【计算直线的交点数】（C语言代码）

C二级辅导-同因查找（C语言代码）

　　评论区

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

不容易系列（C语言代码）

拆分位数（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）