ホームページ >バックエンド開発 >Python チュートリアル >Python での 8 つの一般的な並べ替えアルゴリズムの定義、実装、および時間消費効率分析
Python での 8 つの一般的な並べ替えアルゴリズムの定義、実装、および時間消費効率分析
- 不言オリジナル
- 2018-04-27 11:05:221232ブラウズ
この記事では、主に 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]
選択ソート[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、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、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、9 00 、918、954、976、998]
Tong_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、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, 81, 89, 89, 89, 90]
none
shell_sort に時間がかかる: 0.113964080811
結果は: [5 , 45, 63 、81、83、89、89、89、90]
なし
Tong_sort には時間がかかります: 0.0460147857666
結果は次のようになります: [5、45、46、63、81、83、89、89、89 、90]
なし
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]
---------------------------------------- --- --------------------------------------
ec06c782b828df97a4febeff4963db18 0.113964080811
9cee76b4611194e07b72cdf25a88da0a 0.0259876251221
67a85f6c8f727a543edb0cbc541221ec 0.0209808349609
0685254efcb8af288b22ec8ccffbe514 6968460083
0.0138282775879
0.0460147857666
以上がPython での 8 つの一般的な並べ替えアルゴリズムの定義、実装、および時間消費効率分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。