您的位置:首页 - 教程 - IT技术 - 正文
冒泡排序详解

冒泡排序详解

冒泡排序

一、算法步骤

  • 将第一个数字和第二个数字比较,若第一个数字比第二个数字大,则交换位置。

  • 然后再将第二个数字和第三个数字比较,依次不断地比较,交换。不断循环

  • 直到不再发生交换,这就表明排序已完成,此时得到就是一个有序数列。

二、示例讲解

  • 例如:对一个含有4个元素的数列:6,4,9,5进行从小到大排序

  • 第一趟(第一次循环):

初态 i=0 i=1 i=2
6 4 4 4
4 6 6 6
9 9 9 5
5 5 5 9
  • i=0

  • 第一次先将最前面的两个数6和4比较,6比4大,因此将4和6的位置交换

  • 6,4,9,5 --> 4,6,9,5

  • i=1

  • 第二次再将中间两个数6和9比较,6比9小,无需交换位置。

  • 4,6,9,5

  • i=2

  • 第三次再将后面两个数9和5比较,9比5大,因此将9和5的位置交换

  • 4,6,9,5 --> 4,6,5,9


  • 第二趟(第二次循环):

初态 i=0 i=1 i=2
4 4 4 4
6 6 5 5
5 5 6 6
9 9 9 9
  • i=0

  • 第一次先将最前面的两个数4和6比较,4比6小,无需交换位置

  • 4,6,5,9

  • i=1

  • 第二次再将中间两个数6和5比较,6比5大,因此将6和5的位置交换

  • 4,6,5,9 --> 4,5,6,9

  • i=2

  • 第三次再将后面两个数6和9比较,6比9小,无需交换位置

  • 4,5,6,9


  • 第三趟(第三次循环):

初态 i=0 i=1 i=2
4 4 4 4
5 5 5 5
6 6 6 6
9 9 9 9
  • i=0

  • 第一次先将最前面的两个数4和5比较,4比6小,无需交换位置

  • i=1

  • 第二次先将中间的两个数5和6比较,4比6小,无需交换位置

  • i=2

  • 第三次先将后面的两个数6和9比较,4比6小,无需交换位置

  • 第三趟没有发生交换,表明排序已完成,此时得到就是一个有序数列。

三、算法复杂度

1.时间复杂度

  • 最差情况:要排序的列表完全逆序的情况下,此时时间复杂度为O(n^2)

  • 最好情况:要排序的列表已经排好顺序的情况下,此时只需对列表扫描一次,算法复杂度为O(n)

四、代码实现

  1. /* 
  2. * @author skyward 
  3. */ 
  4. public class BubbleSort
  5.  
  6. public void bubbleSort(int[] numbers)
  7. /** 
  8. * true为有交换;false为无交换 
  9. * 若无交换则表明排序完成,退出循环。否则继续排序 
  10. */ 
  11. boolean numbersSwitched; 
  12. do { 
  13. numbersSwitched = false
  14. for (int i = 0; i < numbers.length - 1; i++) { 
  15. if (numbers[i + 1] < numbers[i]) { 
  16. int tmp = numbers[i + 1]; 
  17. numbers[i + 1] = numbers[i]; 
  18. numbers[i] = tmp; 
  19. numbersSwitched = true


  20. } while (numbersSwitched); 

  21.  
  22. @Test 
  23. public void testBubble()
  24. final int[] numbers = {6, 4, 9, 5}; 
  25. //预期结果 
  26. final int[] expected = {4, 5, 6, 9}; 
  27.  
  28. bubbleSort(numbers); 
  29. assertArrayEquals(expected, numbers); 



评论: