python实现五种排序算法（附代码）
⽂章⽬录
说明：本⽂主要使⽤python实现了五种基本的排序算法（冒泡排序、选择排序、插⼊排序、归并排序、快速排序），并⽐较了每种算法的运⾏耗时，借鉴了
github：
菜鸟教程:
博客园：⼀像素
每种算法的原理请参照上述的教程，写得⾮常简单易懂，此处不再复述算法原理
1. 冒泡排序
算法部分：
def bubbleSort(arr):
for i in range(1,len(arr)):# 轮数
for j in range(0,len(arr)-1):# 每⼀轮的循环⽐较
if arr[j]>arr[j+1]:
arr[j],arr[j+1]= arr[j+1],arr[j]
return arr
测试部分：
import numpy as np
import time
import matplotlib.pyplot as plt
test_list=[10,100,1000,5000,10000]
time_list =[]
print("=="*40)
for test_num in test_list:
list_bubbleSort = np.random.randint(0,1000000,test_num)
start = time.time()
list_bubbleSort=bubbleSort(list_bubbleSort)
end = time.time()
print("{}个正整数排序耗时:{}".format(test_num,(end-start)))
print("=="*40)
time_list.append(end-start)
# 绘制时间曲线
plt.figure()
plt.plot(test_list,time_list,'r')
plt.title('ListSize-SortTime Map')
plt.xlabel('ListSize')
plt.ylabel('SortTime s')
plt.show()
结果部分：
================================================================================ 1000个正整数排序耗时:0.684316873550415
================================================================================ 5000个正整数排序耗时:17.80435299873352
================================================================================ 10000个正整数排序耗时:73.79979467391968
================================================================================
2. 选择排序
算法部分：
def selectionSort(arr):
for i in range(len(arr)-1):
min_index = i # 当前位置作为初始位置
for j in range(i+1,len(arr)):
if arr[j]<arr[min_index]:
min_index = j # 更新最⼩值的索引
if i != min_index:# 如果当前值不是最⼩值位置就替换位置
arr[i], arr[min_index]= arr[min_index], arr[i]
return arr
测试部分：
import numpy as np
import time
import matplotlib.pyplot as plt
test_list=[10,100,1000,5000,10000]
time_list =[]
print("=="*40)
for test_num in test_list:
# ⽣成序列
list_selectionSort = np.random.randint(0,10000,test_num)
start = time.time()
list_selectionSort=selectionSort(list_selectionSort)
end = time.time()
print("{}个正整数排序耗时:{}".format(test_num,(end-start)))
print("=="*40)
time_list.append(end-start)
# 绘制时间曲线
plt.figure()
plt.plot(test_list,time_list,'r')
plt.title('ListSize-SortTime Map')
plt.xlabel('ListSize')
plt.ylabel('SortTime s')
plt.show()
结果部分：
================================================================================ 1000个正整数排序耗时:0.24267196655273438
================================================================================ 5000个正整数排序耗时:6.093706846237183
================================================================================ 10000个正整数排序耗时:25.897886276245117
================================================================================
3. 插⼊排序
算法部分：
def insertSort(arr):
for i in range(len(arr)):
pre_index = i-1
current = arr[i]
while pre_index >=0and arr[pre_index]>current:
# 第⼀个value不执⾏
arr[pre_index+1]=arr[pre_index]#在current之前⽐current⼤的值向后移动
pre_index -=1
arr[pre_index+1]= current
菜鸟教程python2return arr
测试部分：
import numpy as np
import time
import matplotlib.pyplot as plt
test_list=[10,100,1000,5000,10000]
time_list =[]
print("=="*40)
for test_num in test_list:
# ⽣成序列
list_insertSort = np.random.randint(0,10000,test_num)
start = time.time()
list_insertSort=insertSort(list_insertSort)
end = time.time()
print("{}个正整数排序耗时:{}".format(test_num,(end-start)))
print("=="*40)
time_list.append(end-start)
# 绘制时间曲线
plt.figure()
plt.plot(test_list,time_list,'r')
plt.title('ListSize-SortTime Map')
plt.xlabel('ListSize')
plt.ylabel('SortTime s')
plt.show()
结果部分：
================================================================================ 1000个正整数排序耗时:0.18753337860107422
================================================================================ 5000个正整数排序耗时:4.48946475982666
================================================================================ 10000个正整数排序耗时:20.23084306716919
================================================================================
4. 归并排序
算法部分：
def mergeSort(arr):
import math
'''分解'''
if(len(arr)<2):
return arr
middle = math.floor((len(arr))/2)
left,right = arr[0:middle],arr[middle:]# 分解区间
return merge(mergeSort(left),mergeSort(right))# 递归
def merge(left,right):
'''归并'''
result =[]
while left and right:#当两个⼦集都有数值的时候，⽐较其顶部的两个值
if left[0]<= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result
测试部分：
import numpy as np
import time
import matplotlib.pyplot as plt
test_list=[10,100,1000,5000,10000,100000]
time_list =[]
print("=="*40)
for test_num in test_list:
# ⽣成序列
list_mergeSort = np.random.randint(0,10000,test_num).tolist()# 输⼊⼀个list，不要ndarray格式
start = time.time()
list_mergeSort=mergeSort(list_mergeSort)
end = time.time()
print("{}个正整数排序耗时:{}".format(test_num,(end-start)))
print("=="*40)
time_list.append(end-start)
# 绘制时间曲线
plt.figure()
plt.plot(test_list,time_list,'r')
plt.title('ListSize-SortTime Map')
plt.xlabel('ListSize')
plt.ylabel('SortTime s')
plt.show()
结果部分：
================================================================================ 10个正整数排序耗时:0.0
================================================================================ 100个正整数排序耗时:0.0010023117065429688
================================================================================ 1000个正整数排序耗时:0.011028528213500977
================================================================================ 5000个正整数排序耗时:0.05063366889953613
================================================================================ 10000个正整数排序耗时:0.08171701431274414
================================================================================ 100000个正整数排序耗时:2.4911255836486816
================================================================================
5. 快速排序
算法部分：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。