Python|冒泡排序

说明

• 排序的定义

对一序列对象根据某个关键字进行排序。

• 术语说明

稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序 ：所有排序操作都在内存中完成；

外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度 ：一个算法执行所耗费的时间。

空间复杂度 ：运行完一个程序所需内存的大小。

n: 数据规模

In-place: 占用常数内存，不占用额外内存

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

具体算法描述如下：

• 步骤1: 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 步骤2: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 步骤3: 针对所有的元素重复以上的步骤，除了最后一个；
• 步骤4: 重复步骤1~3，直到排序完成。

def bubbleSort(todoList):
    length = len(todoList)
    for i in range(0, length-1):
        for j in range(0, length-1-i):
            if todoList[j + 1] < todoList[j]:
                todoList[j],todoList[j + 1]=todoList[j + 1],todoList[j]
    return todoList

现在对10000个随机生成的数据进行排序，然后比较两者消耗的时间。

t1 = time.time()
new1 = RSort.quickSort(randomList)
# print(new1)
t2 = time.time()
print("快速排序：{}".format(RSort.isRight(randomList,new1)))
print("快速排序耗时：{}".format(t2 - t1))

t3 = time.time()
new2 = RSort.bubbleSort(randomList)
# print(new2)
t4 = time.time()
print("冒泡排序：{}".format(RSort.isRight(randomList,new2)))
print("冒泡排序耗时：{}".format(t4 - t3))

快速排序耗时：0.025930404663085938

冒泡排序耗时：14.162765979766846

插入排序耗时：5.0889317989349365

选择排序耗时：7.227694034576416

堆排序耗时：14.017498254776001