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:	", 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:	", t1 / test_count)

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

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

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

时间复杂度：

冒泡排序：

　　1+2+。。。+n-1 ~ n²/2

插入排序：

　　最优：以及排序好的数组：n-1

　　最差：逆序数组：和冒泡一样，1+2+。。。+n-1 ~ n²/2

归并排序：

　　自己些的分析见下面的文章，时间复杂度：nlogⁿ

　　https://www.cnblogs.com/gsp1004/p/10825941.html

　　多说一句，我最开始以为空间复杂度是nlogⁿ。但实际是n

　　我的错误理解：按照树展开，每层有n个元素，一共logⁿ层，但是并不是这样的，

　　正确的顺序的：归并排序的递归会先将树从左子节点一直执行到最底部的叶子节点，所以空间复杂度：n/2 + n/4 + n/8 + ... + 1 ~ n

快速排序：

　　快排的时间复杂度到底怎么算的现在还是木有搞懂，因为最优就变成了类似归并O(nlogⁿ），最差就变成了类似冒泡O(n²），但是说什么平均时间复杂度是O(nlogⁿ）。。。这个待研究。

　　但是快排是原地排序，不需要开辟新的内存，也就是空间复杂度是0

自己测试的这几个排序的时间：

　　插入和冒泡是一个量级，但是插入快一些。但是数据量大了后，就真的弱爆了。看下面1w数据执行时间对比就知道了。但是数据量小的时候，比如就几十个（30个以内？），差异不大，貌似用插入会更快一点点~~~

　　快排和归并是一个量级，但是快排要快一些。这一点我很费解，为什么快排会快一些？？？有一个坑要研究一下子。。。

100w数据：

<class '__main__.MergeSort'>running time: 6.76003047388366

<class '__main__.FastSort'>running time: 5.620691225466125

10w数据：

<class '__main__.MergeSort'>running time: 0.5305758325035888

<class '__main__.FastSort'>running time: 0.4379082312716691

1w数据：

<class '__main__.MergeSort'>running time: 0.049988164087996834

<class '__main__.FastSort'>running time: 0.032162911379993483

<class '__main__.InsertSort'>running time: 3.9088220416271278

<class '__main__.BubbleSort'>running time: 6.644870537276558

1w数据跑1k次：

test 1000 times, data length is 10000

MergeSort: 3.865276552134844e-05

FastSort: 2.9817472595865978e-05

test 1000 times, data length is 10000

MergeSort: 3.639758325856235e-05

FastSort: 2.8445983728389024e-05