Python의 8가지 일반적인 정렬 알고리즘에 대한 정의, 구현 및 시간 소비 효율성 분석
- 不言원래의
- 2018-04-27 11:05:221255검색
이 글에서는 주로 Python의 8가지 정렬 알고리즘에 대한 정의, 구현 및 시간 소모 효율성 분석을 소개하며, 또한 버블 정렬, 직접 삽입 정렬, 선택 정렬, 병합 정렬, 힐 정렬, 버킷 정렬, 힙을 구체적인 예와 비교합니다. 정렬 등 정렬 알고리즘의 사용 및 실행 효율성에 대해서는 도움이 필요한 친구들이 참고할 수 있습니다
이 기사에서는 Python에서 흔히 사용되는 8가지 정렬 알고리즘에 대한 정의, 구현 및 시간 소비 효율성 분석에 대해 설명합니다. 참고하실 수 있도록 자세한 내용은 다음과 같습니다.
어젯밤에 몇 가지 일반적인 정렬 알고리즘을 요약하기 시작했습니다. 이전에 정렬 알고리즘에 관한 여러 관련 블로그 게시물을 작성했기 때문에 매우 편리하다고 할 수 있습니다. 여기서의 목적은 이러한 정렬 알고리즘에 대해 보다 완전하고 자세한 요약을 제공하고 버블 정렬, 직접 삽입 정렬, 선택 정렬, 병합 정렬, 힐 정렬, 버킷 정렬 및 힙의 기본 사항을 검토하는 것입니다. 종류. 분석하고 구현하기 위한 빠른 정렬부터 시작하겠습니다. 마지막에는 원리와 알고리즘 기초에 중점을 두고 있으며, 그 다음에는 이러한 분야의 숙련도가 향후 작업이나 인터뷰 준비에 중요하지 않습니다. 알고리즘은 내부 의미와 이론적 근거를 이해하는 데 중점을 둡니다. 이를 구현해야만 함정을 피하고 실수를 줄일 수 있습니다. 이는 연습 중에 실수하는 것이 나쁘다는 의미는 아니지만, 가능한 한 실수는 적습니다. 좋은 프로그래밍 습관은 엄격한 제약과 불가분의 관계입니다. 여기서는 자세한 내용을 검토하지 않고 구체적인 구현을 살펴보겠습니다. 설명은 매우 자세해야 합니다. 설명:
#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：八大排序算法
'''
import time
import random
time_dict={}
def time_deco(sort_func):
'''''
时间计算的装饰器函数,可用于计算函数执行时间
'''
def wrapper(num_list):
start_time=time.time()
res=sort_func(num_list)
end_time=time.time()
time_dict[str(sort_func)]=(end_time-start_time)*1000
print '耗时为：',(end_time-start_time)*1000
print '结果为：', res
return wrapper
def random_nums_generator(max_value=1000, total_nums=20):
'''''
随机数列表生成器
一些常用函数：
random随机数生成
random.random()用于生成一个0到1之间的随机数:0 <= n < 1.0；
random.uniform(a, b)，用于生成一个指定范围内的随机符点数，两个参数其中一个是上限，一个是下限。min(a,b) <= n <= max(a,b)；
randdom.randint(a, b), 用于生成一个指定范围内的整数，其中a是下限，b是上限： a<= n <= b；
random.randrange(start, stop, step), 从指定范围内，按指定基数递增的集合获取一个随机数；
random.choice(sequence), 从序列中获取一个随机元素；
random.shuffle(x), 用于将一个列表中的元素打乱；
random.sample(sequence, k), 从指定序列中随机获取指定长度的片断；
'''
num_list=[]
for i in range(total_nums):
num_list.append(random.randint(0,max_value))
return num_list
#@time_deco
def Bubble_sort(num_list):
'''''
冒泡排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
'''
for i in range(len(num_list)):
for j in range(i,len(num_list)):
if num_list[i]>num_list[j]: #这里是升序排序
num_list[i], num_list[j]=num_list[j], num_list[i]
return num_list
#@time_deco
def Insert_sort(num_list):
'''''
直接插入排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
'''
for i in range(len(num_list)):
for j in range(0,i):
if num_list[i]<num_list[j]: #这里是升序排序,跟冒泡排序差别在于，冒泡是向后遍历，这个是向前遍历
num_list[i], num_list[j]=num_list[j], num_list[i]
return num_list
#@time_deco
def Select_sort(num_list):
'''''
选择排序，时间复杂度O(n^2)，空间复杂度O(1)，不是稳定排序
'''
for i in range(len(num_list)):
min_value_index=i
for j in range(i, len(num_list)):
if num_list[j]<num_list[min_value_index]:
min_value_index=j #乍一看，感觉冒泡，选择，插入都很像，选择跟冒泡的区别在于：冒泡是发现大
#小数目顺序不对就交换，而选择排序是一轮遍历结束后选出最小值才交换，效率更高
num_list[i], num_list[min_value_index]=num_list[min_value_index], num_list[i]
return num_list
#@time_deco
def Merge_sort(num_list):
'''''
归并排序，时间复杂度O(nlog₂n)，空间复杂度：O(1)，是稳定排序
'''
if len(num_list)==1:
return num_list
length=len(num_list)/2
list1=num_list[:length]
list2=num_list[length:]
result_list=[]
while len(list1) and len(list2):
if list1[0]<=list2[0]:
result_list.append(list1[0])
del list1[0] #这里需要删除列表中已经被加入到加过列表中的元素，否则最后比较完后列表
else: #中剩余元素无法添加
result_list.append(list2[0])
del list1[0]
if len(list1): #遍历比较完毕后列表中剩余元素的添加
result_list+=list1
else:
result_list+=list2
return result_list
#@time_deco
def Shell_sort(num_list):
'''''
希尔排序，时间复杂度：O(n)，空间复杂度：O(n^2),不是稳定排序算法
'''
new_list = []
for one_num in num_list:
new_list.append(one_num)
count=len(new_list)
step=count/2;
while step>0:
i=0
while i<count:
j=i+step
while j<count:
t=new_list.pop(j)
k=j-step
while k>=0:
if t>=new_list[k]:
new_list.insert(k+1, t)
break
k=k-step
if k<0:
new_list.insert(0, t)
#print '---------本轮结果为：--------'
#print new_list
j=j+step
#print j
i=i+1
#print i
step=step/2 #希尔排序是一个更新步长的算法
return new_list
#@time_deco
def Tong_sort(num_list):
'''''
桶排序，时间复杂度O(1)，空间复杂度与最大数字有关，可以认为是O(n)，典型的空间换时间的做法
'''
original_list = []
total_num=max(num_list) #获取桶的个数
for i in range(total_num+1): #要注意这里需要的数组元素个数总数比total_num数多一个因为下标从0开始
original_list.append(0)
for num in num_list:
original_list[num] += 1
result_list = []
for j in range(len(original_list)):
if original_list[j] != 0:
for h in range(0,original_list[j]):
result_list.append(j)
return result_list
def Quick_sort(num_list):
'''''
快速排序，时间复杂度：O(nlog₂n)，空间复杂度：O(nlog₂n)，不是稳定排序
'''
if len(num_list)<2:
return num_list
left_list = [] #存放比基准结点小的元素
right_list = [] #存放比基准元素大的元素
base_node = num_list.pop(0) #在这里采用pop()方法的原因就是需要移除这个基准结点，并且赋值给base_node这个变量
#在这里不能使用del()方法，因为删除之后无法再赋值给其他变量使用，导致最终数据缺失
#快排每轮可以确定一个元素的位置，之后递归地对两边的元素进行排序
for one_num in num_list:
if one_num < base_node:
left_list.append(one_num)
else:
right_list.append(one_num)
return Quick_sort(left_list) + [base_node] + Quick_sort(right_list)
def Heap_adjust(num_list, i, size):
left_child = 2*i+1
right_child = 2*i+2
max_temp = i
#print left_child, right_child, max_temp
if left_child<size and num_list[left_child]>num_list[max_temp]:
max_temp = left_child
if right_child<size and num_list[right_child]>num_list[max_temp]:
max_temp = right_child
if max_temp != i:
num_list[i], num_list[max_temp] = num_list[max_temp], num_list[i]
Heap_adjust(num_list, max_temp, size) #避免调整之后以max为父节点的子树不是堆
def Create_heap(num_list, size):
a = size/2-1
for i in range(a, -1, -1):
#print '**********', i
Heap_adjust(num_list, i, size)
#@time_deco
def Heap_sort(num_list):
'''''
堆排序，时间复杂度：O(nlog₂n)，空间复杂度：O(1)，不是稳定排序
'''
size=len(num_list)
Create_heap(num_list, size)
i = size-1
while i > 0:
num_list[0], num_list[i] = num_list[i], num_list[0]
size -= 1
i -= 1
Heap_adjust(num_list, 0, size)
return num_list
if __name__ == '__main__':
num_list=random_nums_generator(max_value=100, total_nums=50)
print 'Bubble_sort', Bubble_sort(num_list)
print 'Insert_sort', Insert_sort(num_list)
print 'Select_sort', Select_sort(num_list)
print 'Merge_sort', Merge_sort(num_list)
print 'Shell_sort', Shell_sort(num_list)
print 'Tong_sort', Tong_sort(num_list)
print 'Heap_sort', Heap_sort(num_list)
print 'Quick_sort', Quick_sort(num_list)
# print '-----------------------------------------------------------------------------'
# for k,v in time_dict.items():
# print k, v
결과는 다음과 같습니다:
bubble_sort 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419 , 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 81 3, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Insert_sort [34 , 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Select_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362 , 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 71 8, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Merge_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191 , 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311 , 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 954 , 976, 998]
Shell_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 00 , 918, 954, 976, 998]
통_정렬 [34, 49, 63, 67, 71, 72, 75, 120, 128 , 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 8 85, 894, 900, 918, 954, 976, 998]
Heap_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260 , 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 57 0, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
빠른 정렬 [34, 49, 63, 67, 71, 72 , 75, 120, 128, 181, 185, 191, 202, 217, 241, 257 , 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 5 25, 570, 618, 651, 701, 711, 717, 718, 752, , 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
여기에서는 데코레이터를 사용하지 않습니다. 주로 이 데코레이터에 대해 잘 모릅니다. 빠른 정렬 중에 오류를 보고했지만 보고하지 않았습니다. 다음은 데코레이터 사용 결과에 대한 간단한 테스트 예입니다.
시간이 있으면 데코레이터에 대해 배우고 싶습니다. 데코레이터는 단순히 패턴화된 것들을 위한 인공물이라고 생각하지만, 데코레이터를 사용하는 방법과 작성하는 방법을 알아야 합니다!Bubble_sort에 소요되는 시간: 0.0290870666504
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Insert_sort에 소요되는 시간: 0.0209808349609
결과는 다음과 같습니다. 5 , 45 , 46, 63, 81, 83, 89, 89, 89, 90]
없음
Select_sort에 소요되는 시간: 0.0259876251221
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90 ]
Nonegmerge_sort에는 시간이 걸립니다: 0.0138282775879
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 89, 89, 89, 90]
Sone
shell_sort에는 시간이 걸립니다: 0.11396408080811
결과는: [5 , 4 5, 46 , 63, 81, 83, 89, 89, 89, 90]
없음
Tong_sort에 소요되는 시간: 0.0460147857666
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 83, 89, 89, 89 , 90]
None
Heap_sort에는 시간이 걸립니다: 0.046968460083
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Quick_sort [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
----------------------------- --------------------------
9ea51c619c334b7056c3db049e0c14df 0.113964080811
< ;function Select_sort at 0.02598762512210.0209808349609 . 68460083
0.0138282775879
0.0460147857666
위 내용은 Python의 8가지 일반적인 정렬 알고리즘에 대한 정의, 구현 및 시간 소비 효율성 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!