排序算法一：冒泡排序

文章目录

冒泡排序

冒泡排序需要数据交换位置，所以属于交换排序的一种。

算法原理

对输入数组进行排序，以升序数组为例，对数组进行遍历，比较相邻两个数，将大值移动到后面，遍历完第一次之后能保证最大值放到后面，然后依次递减数组遍历的长度直到数组完全有序。

import random
import time
def bubble_sort(array):
    for i in range(len(array)-1):   #总共进行len(array)-1次遍历
        for j in range(len(array) - i - 1):     #每次遍历要遍历len(array)-i-1个数
            if array[j] > array[j+1]:           #位置相反,交换位置
                array[j], array[j+1] = array[j+1],array[j]
    return array

#生成10000个值在0~10000的随机数
myList=[random.random()*10000 for i in range(10000)]
start_time=time.time()
print(bubble_sort(myList))
#统计使用时间
print(f"--- {time.time() - start_time} seconds ---")

最后排序10000个数，需要9.975126028060913秒。

改进

我们直知道，如果数据后面完全是有序的，那么if array[j] > array[j+1]:就不会成立，这样的话，我们整个数组就是有序的，可以直接返回了，我们可以设置一个标志位flag，来判断数据是否有序。

import random
import time
def bubble_sort(array):
    for i in range(len(array)-1):   #总共进行len(array)-1次遍历
        flag = False
        for j in range(len(array) - i - 1):     #每次遍历要遍历len(array)-i-1个数
            if array[j] > array[j+1]:           #位置相反,交换位置
                flag=True                       #如果这个地方flag不出现的话,flag就是False,那么最后进行判断就可以返回。
                array[j], array[j+1] = array[j+1],array[j]
        if not flag:
            return array
    return array

#生成10000个值在0~10000的随机数
myList=[random.random()*10000 for i in range(10000)]
start_time=time.time()
print(bubble_sort(myList))
#统计使用时间
print(f"--- {time.time() - start_time} seconds ---")

这个用时是10.090549945831299，这是因为数据比较凌乱，这样的改进适合于数据较为规整的情况。