Go實現冒泡排序

  排序：排序是將一組數據，按照一定的順序進行排列的過程。

 排序分類：

  內部排序：指將需要處理的所有數據都加載到內存存儲器中進行排序。包括(交換式排序法、選擇式排序法和插入式排序法)。

  外部排序法： 數據量過大，無法全部加載到內存中，需要借助外部存儲進行排序，包括(合并排序法和直接合并排序法)。

冒泡排序： (Bubble Sorting)基本思想是通過對待排序序列從后向前(從下標較大的元素開始)以此比較相鄰元素的排序碼，若發現逆序則交換，使排序碼較小的元素逐漸從后補移向前部(從下標較大的單元移向單位較小的單元)，就像水底的氣泡一樣逐漸向上冒。

     因為排序的過程中，各元素不斷的接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，因此要在排序過程中設置一個標志flag判斷元素是否進行過交換，從而減少不必要的比較(優化)。

冒泡排序的思路分析：

第一次排序

package main

import "fmt"
//分析冒泡排序

var arr [5]int = [5]int{24,69,80,57,13}
func main()  {
   fmt.Println("排序前",arr)
   tmp := 0 //定義臨時變量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
   }
   fmt.Println("第一次排序后",arr)

}

上面的判斷是直接寫進main()函數中，維護不太方便考慮將其單獨抽出定義一個函數BubbleSort()將數組傳入里面

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定義臨時變量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
   }
   fmt.Println("第一次排序后",(*arr))

}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //傳入數組的地址

}

使用函數方式的編程會使得代碼美觀，同時方便維護。

第二次排序

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定義臨時變量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
      fmt.Println("第一次排序后",(*arr))
   }

   for  i := 0 ;i< 3; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第二次排序后",(*arr))
   }


}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //傳入數組的地址

}


//結果
排序前 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 57 80 13]
第一次排序后 [24 69 57 13 80]
第二次排序后 [24 69 57 13 80]
第二次排序后 [24 57 69 13 80]
第二次排序后 [24 57 13 69 80]

第三次比較

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定義臨時變量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
      fmt.Println("第一次排序后",(*arr))
   }

   for  i := 0 ;i< 3; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第二次排序后",(*arr))
   }
   for  i := 0 ;i< 2; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第三次排序后",(*arr))
   }


}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //傳入數組的地址

}

//結果
排序前 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 57 80 13]
第一次排序后 [24 69 57 13 80]
第二次排序后 [24 69 57 13 80]
第二次排序后 [24 57 69 13 80]
第二次排序后 [24 57 13 69 80]
第三次排序后 [24 57 13 69 80]
第三次排序后 [24 13 57 69 80]

第四次比較

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定義臨時變量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
      fmt.Println("第一次排序后",(*arr))
   }

   for  i := 0 ;i< 3; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第二次排序后",(*arr))
   }
   for  i := 0 ;i< 2; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第三次排序后",(*arr))
   }
   for  i := 0 ;i< 1; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第四次排序后",(*arr))
   }



}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //傳入數組的地址

}


排序前 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 57 80 13]
第一次排序后 [24 69 57 13 80]
第二次排序后 [24 69 57 13 80]
第二次排序后 [24 57 69 13 80]
第二次排序后 [24 57 13 69 80]
第三次排序后 [24 57 13 69 80]
第三次排序后 [24 13 57 69 80]
第四次排序后 [13 24 57 69 80]

  四次外部比較完成，我們觀察得到第一次外部比較中，內部元素比較了4次，為n-1,第二次外部比較時，內部元素比較了3次，為n-2，第三次外部比較時，內部元素比較了2次，為n-3，第四次外部比較時 內部元素比較了1次，為n-4.同時發現我們上面的代碼使用了四次for循環，但是結構一致，可以對其優化成嵌套時循環對其優化。

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定義臨時變量
   for j :=0 ; j < len(arr)-1 ;j++{
      //多次循環遍歷的時候i是越來越小，j是增大的 用len(arry)-i-j實現遍歷
      for  i := 0 ;i< len(arr)-1-j; i++{
         if arr[i] > arr[i+1] {
            tmp = arr[i]
            arr[i] = arr[i+1]
            arr[i+1] = tmp
         }

      }

   }
   fmt.Println("排序后",(*arr))
}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //傳入數組的地址

}

//結果
排序前 [24 69 80 57 13]
排序后 [13 24 57 69 80]

代碼量明顯減少，結構更加清晰