vlambda博客
学习文章列表

我知道你会冒泡排序,但是你会优化冒泡排序吗?


谢谢打开这篇文章的每个你
关注我们 点击右上角 ··· 设为星标
我知道你会冒泡排序,但是你会优化冒泡排序吗?
我知道你会冒泡排序,但是你会优化冒泡排序吗?

在生活中,我们离不开排序,比如我们上学的时候按个头高低排位置,现在我们买东西的时候会按照发货地远近进行排序,或者价格高低排序。

排序看着简单,可是背后藏着很多的算法和思想。在这给大家介绍一下常用的排序算法。

我知道你会冒泡排序,但是你会优化冒泡排序吗?

每次提到排序,绕不开的就是冒泡排序。

冒泡排序(Bubble sort)是一种基础的交换排序。它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

我们先来看一个例子。


我知道你会冒泡排序,但是你会优化冒泡排序吗?


有这么8个数字组成的无序数列[5,8,6,3,9,2,1,7],希望按照从小到大的顺序对其进行排序。

按照冒泡排序的算法,我们需要链路比较相邻纪录的关键字,如果一个元素大于右边相邻元素时,交换他们的位置,当一个元素小于或等于右边元素,位置不变。


我知道你会冒泡排序,但是你会优化冒泡排序吗?我知道你会冒泡排序,但是你会优化冒泡排序吗?我知道你会冒泡排序,但是你会优化冒泡排序吗?我知道你会冒泡排序,但是你会优化冒泡排序吗?我知道你会冒泡排序,但是你会优化冒泡排序吗?我知道你会冒泡排序,但是你会优化冒泡排序吗?


第一趟下来,元素9作为这个数列中最大的元素,就像是汽水里的气泡一样,冒到了最右侧。

再来第二趟:


我知道你会冒泡排序,但是你会优化冒泡排序吗?

我知道你会冒泡排序,但是你会优化冒泡排序吗?

我知道你会冒泡排序,但是你会优化冒泡排序吗?

我知道你会冒泡排序,但是你会优化冒泡排序吗?

我知道你会冒泡排序,但是你会优化冒泡排序吗?


第二次交换结束,8作为未排序中的最大元素被冒到右侧第二位置上。

将未排序的都遍历过之后,所有的元素都会变为有序,这就是冒泡排序的思路。

接下来,我们来实现这个代码,代码非常简单,使用双循环实现。内部循环控制每一轮的最大元素冒泡处理,外部循环控制所有元素的依次排序。


我知道你会冒泡排序,但是你会优化冒泡排序吗?

def bubble_sort(nums):
   for i in range(len(nums) - 1):  # 这个循环负责设置冒泡排序进行的次数
       for in range(len(nums) - i - 1):  # 内部循环控制每一轮的最大元素冒泡处理
           if nums[j] > nums[j + 1]:
               nums[j], nums[j + 1] = nums[j + 1], nums[j]
   return nums


print(bubble_sort([5,8,6,3,9,2,1,7]))
# 输出:[1, 2, 3, 5, 6, 7, 8, 9]


我们来看看冒泡排序的基本性能


我知道你会冒泡排序,但是你会优化冒泡排序吗?


关于稳定性:因为在比较的过程中,当两个相同大小的元素相邻,只比较大或者小,所以相等的时候是不会交换位置的。而当两个相等元素离着比较远的时候,也只是会把他们交换到相邻的位置。他们的位置前后关系不会发生任何变化,所以算法是稳定的。

冒泡排序是一种比较好理解的排序,但是整体的性能相比较来说比较差,因此需要进行优化。

我们来看一个特殊情况


我知道你会冒泡排序,但是你会优化冒泡排序吗?


如果按照上面说的算法去进行计算,我们加一点代码进去看看具体排序情况:


def bubble_sort(nums):

   for i in range(len(nums) - 1):  # 这个循环负责设置冒泡排序进行的次数

       for j in range(len(nums) - i - 1):  # 内部循环控制每一轮的最大元素冒泡处理

           if nums[j] > nums[j + 1]:

               nums[j], nums[j + 1] = nums[j + 1], nums[j]

       print("第", i , "次排序后:", end='')

       for n in nums:

           print(n, end=' ,')

       print(" ")

   return nums

print(bubble_sort([1,3,4,5,6,7,8,9]))


实际输出

第 0 次排序后:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,

第 1 次排序后:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,

第 2 次排序后:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,

第 3 次排序后:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,

第 4 次排序后:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,

第 5 次排序后:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,

第 6 次排序后:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,

[1, 3, 4, 5, 6, 7, 8, 9]


我们能看到在第一次循环的时候,整个数列已经是有序的,但是常规版的算法依然会继续流程,浪费很多的时间,而这些都是多余的。

如果我们能判断出数列已经有序,并且做出标记,那么剩下的几轮排序就不必执行了,可以提前结束工作。我们来改良一下代码:


def bubble_sort(nums):

   for i in range(len(nums) - 1):  # 这个循环负责设置冒泡排序进行的次数

       #有序标记,每一轮的初始值都是True

       is_sorted = True

       for j in range(len(nums) - i - 1):  # 内部循环控制每一轮的最大元素冒泡处理

           if nums[j] > nums[j + 1]:

               #因为有元素进行交换,所以不是有序的,标记变为False

               nums[j], nums[j + 1] = nums[j + 1], nums[j]

               is_sorted = False

       print("第", i , "次排序后:", end='')

       for n in nums:

           print(n, end=' ,')

       print(" ")

       if is_sorted:

           break

   return nums

print(bubble_sort([1,3,4,5,6,7,8,9]))


# 输出:[1, 3, 4, 5, 6, 7, 8, 9]

    加上这个标记位之后,我们再来运行一下:

第 0 次排序后:1 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,

[1, 3, 4, 5, 6, 7, 8, 9]

可以看到,当整体数列已经有序的基础上,不需要再进行后续的多次排序时间浪费了。整体的最好时间就优化为O(n)。


最后祝大家学习愉快。


我知道你会冒泡排序,但是你会优化冒泡排序吗?



Bye~

-------------- Testfan精选 --------------

我就知道你“在看”