Python 冒泡排序，选择排序，归并排序， 希尔排序 算法 及测试

• 使用代码实现冒泡排序，选择排序，归并排序， 希尔排序4中算法完成下列任务。

1. 对1~100000序列打乱顺序，使用上述4种排序算法进行排序。
2. 每种算法排序重复100次
3. 排序过程中记录每次排序所需的时间
4. 统计每一种排序所使用时间的最大值，最小值和平均值。

排序算法

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, '希尔排序')

测试代码

from zy1.SortTest import TestSort

test1 = TestSort(k=5)

test1.test_bubble_sort()
test1.test_selection_sort()
test1.test_merge_sort()
test1.test_shell_sort()
test1.test_quick_sort()

测试结果

快速排序 	 max =4.422002  	 min=1.108573 	 evg=2.153202
希尔排序 	 max =8.791003  	 min=3.210291 	 evg=4.801248
归并排序 	 max =12.64344  	 min=3.401489 	 evg=5.964642
...