冒泡排序

冒泡排序(Bubble Sort) 是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，此时该数列就已经排序完成。个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。

算法原理

冒泡排序算法的原理如下：

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序 - 图1

冒泡算法实现:

  1. func main() {
  2.     var arr = []int{9,10,11,5,3,4,27,2,1,3,20}
  3.     //升序
  4.     bubbleAscendingSort(arr)
  5.     //降序
  6.     bubbleDescendingSort(arr)
  7. }
  9. //升序
  10. func bubbleAscendingSort(arr []int) {
  11.     for i :=0; i < len(arr)-1; i++ {
  12.         for j := i+1; j< len(arr); j++ {
  13.             if (arr[i] > arr[j]) {
  14.                 arr[i],arr[j] = arr[j],arr[i]
  15.             }
  16.         }
  17.     }
  19.     fmt.Println("bubbleAscendingSort:",arr)
  20. }
  22. //降序
  23. func bubbleDescendingSort(arr []int) {
  24.     for i :=0; i < len(arr)-1; i++ {
  25.         for j := i+1; j< len(arr); j++ {
  26.             if (arr[i] < arr[j]) {
  27.                 arr[i],arr[j] = arr[j],arr[i]
  28.             }
  29.         }
  30.     }
  32.     fmt.Println("bubbleDescendingSort:",arr)
  33. }

运行结果:

  1. bubbleAscendingSort: [1 2 3 3 4 5 9 10 11 20 27]
  3. bubbleDescendingSort: [27 20 11 10 9 5 4 3 3 2 1]