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 //定義臨時變數 fori := 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" //分析氣泡排序 funcBubbleSort(arr *[5]int){ fmt.Println("排序前",(*arr)) tmp := 0 //定義臨時變數 fori := 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" //分析氣泡排序 funcBubbleSort(arr *[5]int){ fmt.Println("排序前",(*arr)) tmp := 0 //定義臨時變數 fori := 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)) } fori := 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" //分析氣泡排序 funcBubbleSort(arr *[5]int){ fmt.Println("排序前",(*arr)) tmp := 0 //定義臨時變數 fori := 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)) } fori := 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)) } fori := 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" //分析氣泡排序 funcBubbleSort(arr *[5]int){ fmt.Println("排序前",(*arr)) tmp := 0 //定義臨時變數 fori := 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)) } fori := 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)) } fori := 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)) } fori := 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" //分析氣泡排序 funcBubbleSort(arr *[5]int){ fmt.Println("排序前",(*arr)) tmp := 0 //定義臨時變數 for j :=0 ; j < len(arr)-1 ;j++{ //多次迴圈遍歷的時候i是越來越小,j是增大的 用len(arry)-i-j實現遍歷 fori := 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]
程式碼量明顯減少,結構更加清晰