Python编写排序算法探测器

代码

algorithms.py

import random

# O(n^2)
def selection_sort(lyst, profiler):
    """选择排序"""
    i = 0
    while i < len(lyst) - 1:
        min_index = i
        j = i + 1
        while j < len(lyst):
            profiler.comparison()
            if lyst[j] < lyst[min_index]:
                min_index = j
            j += 1
        if i != min_index:
            profiler.exchange()
            lyst[i], lyst[min_index] = lyst[min_index], lyst[i]
        i += 1


# O(n^2)
def bubble_sort(lyst, profiler):
    """冒泡排序"""
    # 外层循环len(lyst) - 1, j最大能取到倒数第二个值, j+1取到最后一个
    for i in range(1, len(lyst)):
        for j in range(0, len(lyst) - i):
            profiler.comparison()
            if lyst[j] > lyst[j + 1]:
                profiler.exchange()
                lyst[j], lyst[j + 1] = lyst[j + 1], lyst[j]

# O(n^2)
def insertion_sort(lyst, profiler):
    """插入排序"""
    # i=1, 表示假定 lyst[0] 为有序数据, 下一个为无序数据
    for i in range(1, len(lyst)):
        item = lyst[i]
        j = i - 1
        while j >= 0:
            profiler.comparison()
            # 如果待排数据小于lyst[j], 就往后覆盖赋值
            if item < lyst[j]:
                profiler.exchange()
                lyst[j + 1] = lyst[j]
                j -= 1
            # 因为lyst[j] 是当前有序数值中最大的数, 如果比它还大就直接跳出
            else:
                break
        # j 多减了1
        lyst[j + 1] = item

# O(nlogn)
def quick_sort(lyst, profiler):
    quick_sort_helper(lyst, 0, len(lyst) - 1, profiler)

def quick_sort_helper(lyst, left, right, profiler):
    """快速排序"""
    middle = (left + right) // 2
    # 基准点
    pivot = lyst[middle]
    if left < right:
        # 边界
        boundary = left
        # 将基准点与最后一个点交换
        lyst[middle], lyst[right] = lyst[right], lyst[middle]
        # 遍历边界右边, 是否小于基准点
        for index in range(left, right):
            profiler.comparison()
            if lyst[index] < pivot:
                profiler.exchange()
                lyst[boundary], lyst[index] = lyst[index], lyst[boundary]
                boundary += 1
        lyst[boundary], lyst[right] = lyst[right], lyst[boundary]
        # 左右子列表
        quick_sort_helper(lyst, left, boundary - 1, profiler)
        quick_sort_helper(lyst, boundary + 1, right, profiler)

profiler.py

"""
算法探测器

使用方式:
from profiler import Profiler
from algorithms import *

p = Profiler()
p.test(selection_sort, size=15, comp=True)

"""

import time
import random

class Profiler(object):

    def test(self, function, lyst=None, size=10,
            unique=True, comp=True, exch=True,
            trace=False):
        """
        function    函数名
        lyst        列表
        size        大小
        unique      生成列表值是否唯一
        comp        是否计算比较次数
        exch        是否计算交换次数
        trace       是否打印排序后的列表
        """
        self._comp = comp
        self._exch = exch
        self._trace = trace
        if lyst != None:
            self._lyst = lyst
        elif unique:
            self._lyst = [i for i in range(1, size + 1)]
            random.shuffle(self._lyst)
        else:
            self._lyst = []
            for count in range(size):
                self._lyst.append(random.randint(1, size))
        self._exchCount = 0
        self._cmpCount = 0
        self._startClock()
        function(self._lyst, self)
        self._stopClock()
        print(self)

    def exchange(self):
        """交换次数"""
        if self._exch:
            self._exchCount += 1
        if self._trace:
            print(self._lyst)

    def comparison(self):
        """比较次数"""
        if self._comp:
            self._cmpCount += 1

    def _startClock(self):
        """开始时间"""
        self._start = time.time()

    def _stopClock(self):
        """结束时间"""
        self._elapsed_time = round(time.time() - self._start, 3)

    def __str__(self):
        """结果"""
        result = "Problem size: "
        result += str(len(self._lyst)) + "\n"
        result += "Elapsed time: "
        result += str(self._elapsed_time) + "\n"
        if self._comp:
            result += "Comparison: "
            result += str(self._cmpCount) + "\n"
        if self._exch:
            result += "Exchanges: "
            result += str(self._exchCount) 
        return result

运行示例：

比较下选择排序和快速排序的速度：