Python 冒泡排序，选择排序，归并排序， 希尔排序 算法 及测试
public-time:2022-10-07 10:49
- 使用代码实现冒泡排序，选择排序，归并排序， 希尔排序4中算法完成下列任务。
- 对1~100000序列打乱顺序，使用上述4种排序算法进行排序。
- 每种算法排序重复100次
- 排序过程中记录每次排序所需的时间
- 统计每一种排序所使用时间的最大值，最小值和平均值。
排序算法
class Sort:
@staticmethod
def bubble_sort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr) - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
@staticmethod
def quick_sort(arr, i=None, j=None):
if i is None:
i = 0
if j is None:
j = len(arr) - 1
if i >= j:
return arr
pivot = arr[i]
low = i
high = j
while i < j:
while i < j and arr[j] >= pivot:
j -= 1
arr[i] = arr[j]
while i < j and arr[i] <= pivot:
i += 1
arr[j] = arr[i]
arr[j] = pivot
Sort.quick_sort(arr, low, i - 1)
Sort.quick_sort(arr, i + 1, high)
return arr
@staticmethod
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
@staticmethod
def merge_sort(arr):
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 math
if len(arr) < 2:
return arr
middle = math.floor(len(arr) / 2)
left, right = arr[0:middle], arr[middle:]
return merge(Sort.merge_sort(left), Sort.merge_sort(right))
@staticmethod
def shell_sort(arr):
n = len(arr)
gap = int(n / 2)
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap = int(gap / 2)
return arr
测试类
import datetime
import random
import threading
from copy import copy
from numpy import mean
from zy1.Sort import Sort
# 生成1~100000
class TestSort:
def __init__(self, k=1):
'''
:param k: 生成 数列的范围: [i for i in range(1, 10 ** k+1)]
'''
self.arr = [i for i in range(1, 10 ** k + 1)]
def fc2(self, func, des: str):
"""
:param func: 排序方法
:param des: 对当前排序方法的描述用于输出提示
:return:
"""
def tis(sort_fun, des):
times = []
arr1 = copy(self.arr)
for i in range(100):
random.shuffle(arr1)
t1 = datetime.datetime.now()
sort_fun(arr1)
t2 = datetime.datetime.now() - t1
times.append(t2.total_seconds())
else:
evg = round(float(mean(times)), 6)
print(f'{des} \t max ={max(times)} \t min={min(times)} \t evg={evg}')
t1 = threading.Thread(target=tis, args=(func, des))
t1.start()
print(f"{des} 线程id:{t1.native_id}")
def test_bubble_sort(self):
self.fc2(Sort.bubble_sort, '冒泡排序')
def test_quick_sort(self):
self.fc2(Sort.quick_sort, '快速排序')
def test_selection_sort(self):
self.fc2(Sort.selection_sort, '选择排序')
def test_merge_sort(self):
self.fc2(Sort.merge_sort, '归并排序')
def test_shell_sort(self):
self.fc2(Sort.shell_sort, '希尔排序')