关注码农话题
做一个实实在在的内行人

冒泡排序算法

冒泡排序是一个简单的排序算法。这个排序算法是基于比较算法,其中每对相邻元件的比较和元素,如果它们不按顺序则交换位置。这个算法是不适合大的数据集,它平均值和最坏情况的复杂性是O(n2),其中n是项目的排位。

算法

我们假定列表是n个元素的阵列。我们进一步假设 swap函数,交换给定数组元素的值。

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

伪代码

我们观察算法,冒泡排序比较每对数组元素,除非整个阵列完全是升序排列。这可能会导致几个复杂的问题,如果数组不需要更多的交换,因为所有的元素都已经升序顺序。

为了缓解这个问题,我们用换一个的标志变量,它会帮助我们,看是否有交换的发生与否。如果没有交换的发生,即数组不需要更多的处理进行排序,它会跳出循环。

气泡排序算法的伪代码可写成如下 –

procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list[j] > list[j+1] then
            /* swap them */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
   end for
   
end procedure return list

实现

还有一个问题,我们并没有在原来的算法及其简易伪地址,也就是说,在每次迭代后的最高值,位于数组的结尾。所以,下一次迭代需要不包括已排序的元素。为了这个目的,在我们的实现中限制了内循环,以避免已排序值。


入职你的梦想 VS 变现你的技术

IT面试宝典码农市场