python 冒泡排序，插入排序，归并排序，快速排序实现code

import time
import random

time.clock()

class BubbleSort(object):
    """冒泡排序算法"""
    def sort_inc(self, nums):
        """如果数组长度为n，那么时间复杂度：
        一共比较n-1次，
        第X次     比较次数
        1           n-1
        2           n-2
        ...
        n-1         1
        时间复杂度为比较次数的和：1 + 2 + 3 + 。。。。 + n-1 = n(n-1)/2
        复杂度去除常数和低阶项，结果是O(n^2)
        """
        length = len(nums)
        if length == 1:
            return nums
        for i in range(length-1):
            for j in range(i+1, length):
                if nums[i] > nums[j]:
                    nums[i], nums[j] = nums[j], nums[i]
        return nums


class InsertSort(object):
    """插入排序算法"""
    def sort_inc(self, nums):
        """如果数组长度为n，那么时间复杂度：
        一共比较n-1次，数组元素从1 -> n-1
        第X次     比较次数
        1           <=1
        2           <=2
        ...
        n-1         <= n-1
        时间复杂度为比较次数的和：1 + 2 + 3 + 。。。。 + n-1 = n(n-1)/2
        复杂度去除常数和低阶项，结果是O(n^2)"""
        length = len(nums)
        if length == 1:
            return nums
        for i in range(1, length):
            key = nums[i]
            for j in range(i-1, -1, -1):
                if key < nums[j]:
                    nums[j+1] = nums[j]
                else:
                    nums[j+1] = key
                    break  # 从这里退出循环是不会执行下面的else的
            else:  # 不是从break退出的，所以所有的数字都比key大，key应该放在第一个
                nums[0] = key
        return nums


class MergeSort(object):
    """合并排序"""
    def sort_inc(self, nums):
        length = len(nums)
        if length == 1:
            return nums

        sorted_num1 = self.sort_inc(nums[:length >> 1])
        sorted_num2 = self.sort_inc(nums[length >> 1:])

        # 将1和2排序
        length1 = len(sorted_num1)
        length2 = len(sorted_num2)
        l1 = 0
        l2 = 0
        ret = []
        while True:
            if l1 < length1 and l2 < length2:
                if sorted_num1[l1] < sorted_num2[l2]:
                    ret.append(sorted_num1[l1])
                    l1 += 1
                else:
                    ret.append(sorted_num2[l2])
                    l2 += 1
            elif l1 == length1:
                ret += sorted_num2[l2:]
                break
            elif l2 == length2:
                ret += sorted_num1[l1:]
                break
            else:
                print("ERROR: l1 = %d, l2 = %d" % (l1, l2))
                exit(-1)
        return ret


class FastSort(object):
    def sort_inc(self, nums, left, right):
        if left >= right:
            return

        key = nums[left]  # 记录基准值
        keng = left  # 记录坑的索引值
        i = left
        j = right

        # 填坑，退出循环时i = j = keng
        while i < j:
            # 从右往左找小值
            while i < j:
                if nums[j] < key:  # 找到小值拿去填坑，将坑至于当前位子
                    nums[keng] = nums[j]
                    keng = j
                    break
                j -= 1

            # # 从左往右找大值
            while i < j:
                if nums[i] > key:
                    nums[keng] = nums[i]
                    keng = i
                    break
                i += 1

        # 坑填完后，把key填到坑里
        nums[keng] = key
        self.sort_inc(nums, left, keng-1)
        self.sort_inc(nums, keng+1, right)

        return nums


def test_func(className, *args):
    test = className()
    begin = time.clock()
    ret = test.sort_inc(*args)
    end = time.clock()
    cost_time = end - begin
    print(str(className) + "running time:\t", cost_time)
    return ret, cost_time


mt = 0
ft = 0
it = 0
bt = 0

# 是否测试
isMergeSort, isFastSort, isInsertSort, isBubbleSort = True,  True,  False, False

test_count = 1000  # 测试次数
data_length = 10000  # 生成测试数据个数

for x in range(test_count):
    # random test data
    testlist = []
    for i in range(data_length):
        testlist.append(random.randint(1, 1000000))  # 测试数据范围

    # test part       #############################################
    if isMergeSort:
        l1, t1 = test_func(MergeSort, testlist.copy())
        mt += t1

    if isFastSort:
        l2, t2 = test_func(FastSort, testlist.copy(), 0, len(testlist) - 1)
        ft += t2

    if isInsertSort:
        l3, t3 = test_func(InsertSort, testlist.copy())
        it += t3

    if isBubbleSort:
        l4, t4 = test_func(BubbleSort, testlist.copy())
        bt += t4

print("test %d times, data length is %d" % (test_count, data_length))
if isMergeSort:
    print("MergeSort:\t", t1 / test_count)

if isFastSort:
    print("FastSort:\t", t2 / test_count)

if isInsertSort:
    print("InsertSort:\t", t3 / test_count)

if isBubbleSort:
    print("BubbleSort:\t", t4/test_count)