數組的排序

排序的基本介紹

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

1. 內部排序：
   1. 一次性
   2. 適用數據量小的情況
      將需要處理的數據都加載到內部存儲器中進行排序。包括交換式排序，選擇式排序，插入式排序
2. 外部排序：
   1. 多次
   2. 適用數據量大的情況
      數據量過大，無法全部加載到內存中，需要借助外部存儲進行排序。包括合并排序法，直接合并排序法

交換式排序

交換式排序是內部排序的一種，運用數值比較后，依據判定規則對數據位置進行交換，以達到排序目的
交換式排序有兩種

1. 冒泡排序
2. 快速排序

冒泡排序法

冒泡排序的思想：
以遞增排序為例，冒泡排序有兩種思路：一種是從前向后遍歷每次循環都將尚未排序的部分中的最大值放到未排序部分的最后一位；一種是從后向前遍歷，每次都將位排序部分的最小值放到未排序部分的最前面

冒泡排序是需要雙層循環來實現的

1. 外層循環控制要幾次將指定數據放到指定位置（最不理想次數也就是len()-1次）
2. 內層循環控制要想將本輪的指定數據放到指定位置所需要逐個比較數據的次數（最不理想次數也就是len()-i，其中i表示第幾次外循環）

優化

只需要本次內部循環沒有改變任何數據的位置，就可以說明數組已經排序完畢了，也就可以提前結束內外雙循環，從而優化代碼。（可以通過設置flag來判斷是否有改變數據位置）

冒泡代碼

package main

import (
“fmt”
)

func BubbleSort(a *[5]int) {
leng := len((*a))
fmt.Printf(“排序前：%v\n”, (*a))
for i := 0; i < leng-1; i++ {
flag := false
for j := 0; j < leng-1-i; j++ {
if (*a)[j] > (*a)[j+1] {
c := (*a)[j]
(*a)[j] = (*a)[j+1]
(*a)[j+1] = c
if !flag {
flag = true
}
}
}
if !flag {
return
}
}
}
func main() {
a := [5]int{4, 12, 532, 1, 23}
BubbleSort(&a)
fmt.Printf(“排序后：%v”, a)
}
輸出結果：
排序前：[4 12 532 1 23]
排序后：[1 4 12 23 532]

數組的查找

1. 順序查找
2. 二分查找

二分查找

二分查找是對一個有序數列進行的。

二分查找的思路

數組a是一個有序數組，假設是遞增的
left=0,right=len(a)-1
mid=(left+right)/2

1. mid<find left=mid+1
2. mid>find right=mid-1
3. mid=find return
4. 123是遞歸進行的
   如果left>right，就說明找不到這個值。

代碼實現

func BinaryFind(arr [6]int, left int, right int, find int) int {
if left > right {
return -1
}
midd := (left + right) / 2
mid := arr[midd]
if mid > find {
return BinaryFind(arr, left, midd-1, find)
} else if mid < find {
return BinaryFind(arr, midd+1, right, find)
} else {
return midd
}
}
func main() {
a := [6]int{1, 3, 6, 8, 10, 21}
index := BinaryFind(a, 0, len(a)-1, 8)
fmt.Printf(“%d”, index)
}