|必拿offer系列|算法|你真的会写冒泡法吗?

什么是冒泡法?

冒泡法是基本排序算法的一种,它是稳定的排序算法,其时间复杂度是O(n^2)

下面引用冒泡法的wiki解释

冒泡排序(英语:Bubble Sort)又称为泡式排序,是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

我现在使用go语言来实现一下go版本的一般性的冒泡法:

for i := 0; i < len(arr);i++ {
  for j := 0; j < len(arr)-1-i;j++{
      if arr[j] > arr[j+1] {
      swap(arr,j,j+1)
      }
  }
}

那么这个算法就这么结束了吗?

冒泡排序的优化

我们知道冒泡法的基本原理就是不断的比较,当把所有的数据都比较结束后,这个排序才算结束,所以每次内层的for就是一次冒泡的过程,每次都少1,然后直到最后一个数据,这样看来数据是依次减少的。外层是n,内部依次是n n-1 n-2 ....1,所以它实际的执行过程的和是

n + n-1 + n-2 ...+1
//加在一起就是 
n x n - (1+...n)
= (n^2 -  n)x0.5

那么我们就发现了这个执行的过程是外面n里面也约等于n,一定是n吗?一定要执行n次吗?

如果某一次的冒泡过程全员未动,不就意味着排序结束吗?

优化代码实现

for i := 0; i < len(arr); i++ {
  f := false
  for j := 0;j < len(arr) -1 - i;j++ {
  if arr[j] < arr[j+1]{
      swap(arr,j,j+1)
      f = true
    }
  }
  // 如果某一次执行完毕了还是false,那么就证明这一次压根没有进行交换
  // 也就是说已经排序结束了,可以跳出了。
  if !f {
  break
  }
}

这个小小的优化如果在数据量大以及前面数据都是顺序的情况下,可以节约非常多的时间。这种小优化在面试的时候也能让面试官眼前一亮,觉得你好牛逼。😄

当然也有垃圾面试官,我的就是,他直接质疑我错了,直到1分钟后,他直接要了我。。。emm。。。选择公司要谨慎。。。

欢迎添加公众号一起学编程!

共 0 个回复