Go實現(xiàn)冒泡排序

  排序：排序是將一組數(shù)據(jù)，按照一定的順序進(jìn)行排列的過程。

 排序分類：

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

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

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

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

冒泡排序的思路分析：

第一次排序

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)

}

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

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)  //傳入數(shù)組的地址

}

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

第二次排序

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)  //傳入數(shù)組的地址

}


//結(jié)果
排序前 [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)  //傳入數(shù)組的地址

}

//結(jié)果
排序前 [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)  //傳入數(shù)組的地址

}


排序前 [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]

  四次外部比較完成，我們觀察得到第一次外部比較中，內(nèi)部元素比較了4次，為n-1,第二次外部比較時，內(nèi)部元素比較了3次，為n-2，第三次外部比較時，內(nèi)部元素比較了2次，為n-3，第四次外部比較時 內(nèi)部元素比較了1次，為n-4.同時發(fā)現(xiàn)我們上面的代碼使用了四次for循環(huán)，但是結(jié)構(gòu)一致，可以對其優(yōu)化成嵌套時循環(huán)對其優(yōu)化。

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定義臨時變量
   for j :=0 ; j < len(arr)-1 ;j++{
      //多次循環(huán)遍歷的時候i是越來越小，j是增大的 用len(arry)-i-j實現(xiàn)遍歷
      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)  //傳入數(shù)組的地址

}

//結(jié)果
排序前 [24 69 80 57 13]
排序后 [13 24 57 69 80]

代碼量明顯減少，結(jié)構(gòu)更加清晰