16 April 2013

如果一个队列只有两个元素且为逆序,只要将这两个元素交换即可。冒泡排序就是一种基于“交换”思想的排序方法,每次比较两个元素,如果为逆序,就将其交换。而这两个元素的选取,就是遍历整个队列来得到。

冒泡排序一般步骤:

  • 第一趟冒泡。遍历整个队列,将当前元素和身后的元素进行比较,逆序的进行交换。这样会进行(n-1)次;
  • 然后再进行遍历冒泡,直到该趟遍历过程中没有发生交换操作为止,此时队列已为正序。

冒泡排序特性:

  • 冒泡的过程中,每一次交换都是大元素向下移动,小元素向上移动,所以整个一趟排序的趋势就是大元素向下移动,小元素想上移动。因为在每一次交换的过程中,大元素都会被交换到下方,所以,一趟排序结束之后,都会有一个当前队列中最大的元素被交换到了队列最后,到达最终位置。
  • 如果该队列为逆序,那就需要遍历(n-1)趟,一共sum_{i=n}^{2}(i-1)比较;如果为正序,那么只需要遍历一趟,进行(n-1)比较即可。平均时间复杂度是O(n^{2});
  • 该排序方法是就地排序,只是在交换的过程中需要申请一个临时变量,一个变量来记录当前遍历是否发生过交换操作,所以空间复杂度是O(1);
  • 冒泡排序基于交换的思想,所以可以保证两个相同的元素不会被交换,该算法是稳定的。

冒牌排序实例:

  • 初始序列:{49, 38, 65, 97, 76, 13, 27, 49}
  • {38, 49, 65, 97, 76, 13, 27, 49} 元素49和38进行比较,逆序,交换;
  • {38, 49, 65, 76, 97, 13, 27, 49} 元素49行业64进行比较,正序,不交换;
  • {38, 49, 65, 76, 13, 27, 97, 49} 元素65和76进行比较,正序;
  • {38, 49, 65, 76, 13, 27, 49, 97} 元素76和13进行比较,逆序,交换;
  • {38, 49, 65, 13, 76, 27, 49, 97} 元素76和27进行比较,逆序,交换;
  • {38, 49, 65, 13, 27, 76, 49, 97} 元素76和49进行比较,逆序,交换;
  • {38, 49, 65, 13, 27, 49, 76}, 97 元素76和97进行比较,正序,不交换。一趟遍历结束,97到达最终位置;
  • {38, 49, 13, 27, 49, 65}, 76, 97 第二趟排序,76到达最终位置;
  • {38, 13, 27, 49, 49}, 65, 76, 97 第三趟排序结束,选出了65;
  • {13, 27, 38, 49}, 49, 65, 76, 97 第四趟排序
  • {13, 27, 38}, 49, 49, 65, 76, 97 第五趟排序
  • {13, 27}, 38, 49, 49, 65, 76, 97 第六趟排序
  • 13, 27, 38, 49, 49, 65, 76, 97 最终结果

原文链接:冒泡排序(BUBBLE SORT),转载请注明来源!

EOF

欢迎加微信交流与吐槽



本站总访问量次; 本站访客数人次; 本文总阅读量次;