python实现简单排序算法
算法
递归两个特点：
调用自身
有穷调用
计算规模越来越小，直至最后结束
用装饰器修饰一个递归函数时会出现问题，这个问题产生的原因是递归的函数也不停的使用装饰器。
解决方法是，只让装饰器调用一次即可，那么可以出创建一个新的普通函数，执行一下递归函数，并放回递归函数的返回值，给这个普通函数加上装饰器即可。
尾递归和正常循环时间复杂度相同，尾递归：每次递归尾部return递归函数
算法关键：
有序区和无序区，随着算法的推进，有序区越来越大，无序区越来越小，直至消失，完成排序
代码：
import random
import time
import sys
import copy
#装饰器
def time_cost(func):
def wrapper(*args,**kwargs):
sTime = time.time()
func(*args,**kwargs)
print("Time cost:%s"%(time.time()-sTime))
print(args[0])
return wrapper
#冒泡排序：
#每一次循环从端点处比较n次选出最大或最小的数，一趟结束n--，每次里层循环n-i-1次。
@time_cost
def bubble_sort(list):
print("\nbubble_sort:")
for i in range(len(list)-1):
tag = 0
for j in range(len(list)-i-1):
if list[j] > list[j+1]:
list[j],list[j+1] = list[j+1],list[j]
tag = 1
if not tag:
return
#选择排序
#每次选出最小的数，放在n，每趟结束n++，每次里层循环（i+1，len（list））
@time_cost
def select_sort(list):
print("\nselect_sort:")
for i in range(len(list)-1):
min = i
for j in range(i+1,len(list)):
if list[min] > list[j]:
min = j
if min != i:
list[i],list[min] = list[min],list[i]
#插入排序
#分有序区和无序区，列表前面是有序区，后面是无序区，每次从无序区的首位取一个元素，与有序区元素依次比较，放到合适的位置，直到无序区元素取完
@time_cost
def insert_sort(list):
print("\ninsert_sort:")
for i in range(len(list)):
tag = 0
for j in range(i,0,-1):
if list[j] < list[j-1]:
list[j],list[j-1] = list[j-1],list[j]
tag = 1
if not tag:
break
#快速排序
#递归实现，取一个数（列表第一个），使得列表左边的元素比此数都小，列表右边的元素比此数都大，依据此数位置切割出左右两边列表分别进行递归，直至列表只有一个元素
def part_sort(list,left,right):
temp = list[left]
while left < right:
while left < right and temp <= list[right]:
right -= 1
list[left] = list[right]
while left < right and temp >= list[left]:
left += 1
list[right] = list[left]
list[left] = temp
return left def _quckly_sort(list,left,right):
if left < right:
mid = part_sort(list,left,right)
_quckly_sort(list,left,mid-1)
_quckly_sort(list,mid+1,right) @time_cost
def quckly_sort(list):
print("\nquckly_sort:")
return _quckly_sort(list,0,len(list)-1)
#快排的时间复杂度为O(nlogn)
#冒泡、选择、插入排序的时间复杂度为O(n^2)
#一般来说处理大数据排序问题，快排比前面三种排序快好几个数量级
#但是如果碰到极端情况，例如：列表是反序排列的
#快排的时间复杂度退化成O(n^2)
#由于自身有递归加大开销，会使相同排序比其他三种排序耗时更久
#系统自带排序 sort()
#大多数编程语言系统排序使用的都是快速排序
#python系统自带的排序使用的是C语言编写的快排，比python写的快排快一个数量级
sort(list)
#一般来说系统都有限制最大递归层数
#修改系统最大递归层数
import sys
sys.setrecursionlimit(10000)
#比较4种排序，当排序个数为10000时
#bubble_sort:
#Time cost:17.794017791748047
#select_sort:
#Time cost:5.8113322257995605
#insert_sort:
#Time cost:15.441883087158203
#_quckly_sort:
#Time cost:0.044002532958984375
#快排效率非常高
#堆排序
#当各节点是顺序存储时,且必须是完全二叉树
#父节点与左孩子关系： i ~ 2i+1
#父节点与右孩子关系： i ~ 2i+2
#首先将列表元素建堆，形成大根堆
#然后循环调整大根堆，取堆顶元素，生成有序序列
#时间复杂度O(nlogn)
def sift(list,low,high):
i = low
j = 2 * i + 1
temp = list[i]
while j <= high:
if j < high and list[j] < list[j+1]:
j += 1
if temp < list[j]:
list[i] = list[j]
i = j
j = 2 * i + 1
else:
break
list[i] = temp
list[low],list[high] = list[low],list[high] @time_cost
def heap_sort(list):
print("\nheap_sort:")
n = len(list)
for i in range(n // 2 - 1, -1, -1):
sift(list, i, n - 1)
for i in range(n-1, -1, -1):
list[0],list[i] = list[i],list[0]
sift(list, 0, i - 1)
#归并排序
#一次归并，将两个排序好的列表合并成一个有序列表
#首先将一个无序列表递归分解成只有1个元素的n个列表
#将所有分解的列表两两执行一次归并算法，最终合成一个有序列表
#时间复杂度O(nlogn)
#空间复杂度O(n)每个一次归并都创建一个列表
def ont_megre_sort(list,low,mid,high):
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high:
if list[i] < list[j]:
ltmp.append(list[i])
i += 1
else:
ltmp.append(list[j])
j += 1
while i <= mid:
ltmp.append(list[i])
i += 1
while j <= high:
ltmp.append(list[j])
j += 1
list[low:high+1] = ltmp def _megre_sort(list,low,high):
if low < high:
mid = (low+high)//2
_megre_sort(list,low,mid)
_megre_sort(list,mid+1,high)
ont_megre_sort(list,low,mid,high) @time_cost
def megre_sort(list):
print("\nmegre_sort:")
return _megre_sort(list,0,len(list)-1)
#一般来说 快速排序 < 归并排序 < 堆排序
#快排极端情况下速度慢，不稳定
#归并排序需要空间开销
#堆排序相对稳定
#时间复杂度O(n)
#希尔排序
#一种分组插入排序算法
#根据定义d为间隔分组，对每个小分组做一次直接插入排序
#d逐渐缩小，列表相对有序，直至d=1，成为直接插入排序，最后一次循环使列表彻底有序
#时间复杂度O((1+T)n)=O(1.3n)
@time_cost
def shell_sort(list):
print("\nshell_sort:")
gap = len(list) // 2
while gap > 0:
for i in range(gap,len(list)):
temp = list[i]
j = i - gap
while j >= 0 and temp < list[j]:
list[j + gap] = list[j]
j -= gap
list[j + gap] = temp
gap //= 2
#----------------------------------------------总结------------------------------------------------#
# 排序方法 时间复杂度 稳定性 代码复杂度 #
# #
# 最坏情况 平均情况 最好情况 #
# 冒泡排序 O(n^2) O(n^2) O(n) 稳定 简单 #
# #
# 直接选择排序 O(n^2) O(n^2) O(n^2) 不稳定 简单 #
# #
# 直接插入排序 O(n^2) O(n^2) O(n^2) 稳定 简单 #
# #
# 快速排序 O(n^2) O(nlogn) O(nlogn) 不稳定 较复杂 #
# #
# 堆排序 O(nlogn) O(nlogn) O(nlogn) 稳定 复杂 #
# #
# 归并排序 O(nlogn) O(nlogn) O(nlogn) 稳定 较复杂 #
# #
# 希尔排序 O(1.3n) 不稳定 较复杂 #
# #
# #
#-----------------------------------------------------------------------------------------------------------------------------#
全部代码
__author__ = 'cq' import time
import random
import sys
import copy def time_cost(func):
def wrapper(*args,**kwargs):
sTime = time.time()
func(*args,**kwargs)
print("Time cost:%s"%(time.time()-sTime))
print(args[0])
return wrapper #-------------------冒泡排序-----------------------#
@time_cost
def bubble_sort(list):
print("\nbubble_sort:")
for i in range(len(list)-1):
tag = 0
for j in range(len(list)-i-1):
if list[j] > list[j+1]:
list[j],list[j+1] = list[j+1],list[j]
tag = 1
if not tag:
return #-------------------插入排序-----------------------#
@time_cost
def insert_sort(list):
print("\ninsert_sort:")
for i in range(len(list)):
tag = 0
for j in range(i,0,-1):
if list[j] < list[j-1]:
list[j],list[j-1] = list[j-1],list[j]
tag = 1
if not tag:
break #-------------------选择排序-----------------------#
@time_cost
def select_sort(list):
print("\nselect_sort:")
for i in range(len(list)-1):
min = i
for j in range(i+1,len(list)):
if list[min] > list[j]:
min = j
if min != i:
list[i],list[min] = list[min],list[i] #-------------------快速排序-----------------------#
def part_sort(list,left,right):
temp = list[left]
while left < right:
while left < right and temp <= list[right]:
right -= 1
list[left] = list[right]
while left < right and temp >= list[left]:
left += 1
list[right] = list[left]
list[left] = temp
return left def _quckly_sort(list,left,right):
if left < right:
mid = part_sort(list,left,right)
_quckly_sort(list,left,mid-1)
_quckly_sort(list,mid+1,right) @time_cost
def quckly_sort(list):
print("\nquckly_sort:")
return _quckly_sort(list,0,len(list)-1) #-------------------堆排序-----------------------#
def sift(list,low,high):
i = low
j = 2 * i + 1
temp = list[i]
while j <= high:
if j < high and list[j] < list[j+1]:
j += 1
if temp < list[j]:
list[i] = list[j]
i = j
j = 2 * i + 1
else:
break
list[i] = temp
list[low],list[high] = list[low],list[high] @time_cost
def heap_sort(list):
print("\nheap_sort:")
n = len(list)
for i in range(n // 2 - 1, -1, -1):
sift(list, i, n - 1)
for i in range(n-1, -1, -1):
list[0],list[i] = list[i],list[0]
sift(list, 0, i - 1) #-------------------归并排序-----------------------#
def ont_megre_sort(list,low,mid,high):
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high:
if list[i] < list[j]:
ltmp.append(list[i])
i += 1
else:
ltmp.append(list[j])
j += 1
while i <= mid:
ltmp.append(list[i])
i += 1
while j <= high:
ltmp.append(list[j])
j += 1
list[low:high+1] = ltmp def _megre_sort(list,low,high):
if low < high:
mid = (low+high)//2
_megre_sort(list,low,mid)
_megre_sort(list,mid+1,high)
ont_megre_sort(list,low,mid,high) @time_cost
def megre_sort(list):
print("\nmegre_sort:")
return _megre_sort(list,0,len(list)-1) #-------------------希尔排序-----------------------#
@time_cost
def shell_sort(list):
print("\nshell_sort:")
gap = len(list) // 2
while gap > 0:
for i in range(gap,len(list)):
temp = list[i]
j = i - gap
while j >= 0 and temp < list[j]:
list[j + gap] = list[j]
j -= gap
list[j + gap] = temp
gap //= 2 def main():
#生成列表
list0 = list(range(100))
first_name = ["陈","张","李","王","赵"]
second_name = ["冰","鑫","程","爱","暖"]
third_name = ["强","国","明","风","芬"]
listname = [
{"id":""+str(i),
"name":random.choice(first_name)+
random.choice(second_name)+
random.choice(third_name),
"age":random.randint(16,60)
} for i in range(10)
]
random.shuffle(list0)
random.shuffle(listname) #copy四份打乱后的列表
list1 = copy.deepcopy(list0)
list2 = copy.deepcopy(list0)
list3 = copy.deepcopy(list0)
list4 = copy.deepcopy(list0)
list5 = copy.deepcopy(list0)
list6 = copy.deepcopy(list0)
list7 = copy.deepcopy(list0) #设置递归深度
sys.setrecursionlimit(10000) print("sort_list:")
print(list0) #排序算法
bubble_sort(list1)
select_sort(list2)
insert_sort(list3)
quckly_sort(list4)
heap_sort(list5)
megre_sort(list6)
shell_sort(list7) print("\npractice to sort this list:")
for i in listname:
print(i) if "__main__" == __name__:
main()
最新文章
- jQuery系列：五个模块总结
- CSS 如何使DIV层水平居中
- programing Python --Sys module
- 移动web开发框架
- Eclipse 启动Tomcat 超时报错的解决方案
- NEFU 2016省赛演练一 F题 (高精度加法)
- [Flex] IFrame系列 —— 在flex的web应用中嵌入html的方法
- vitrualbox虚拟机64位安装报错解决
- UINavigationBar导航栏相关设置
- tomcat错误信息解决方案【严重:StandardServer.await: create[8005]
- SEO_Alexa排名
- Cross-site scripting
- CSS3添加属性选择： [attribute*=value] 、[attribute^=value] 和[attribute$=value]
- CodeForces 721B
- springboot+thymeleaf（2）
- break and continue
- SpringMVC源码情操陶冶-AbstractUrlHandlerMapping
- hadoop中集群节点ID不一致（ java.io.IOException: Incompatible clusterIDs ）
- PHP 图片base64 互转
- Java学习之--List和ArrayList