冒泡排序：
時間復雜度：O(n^2)
穩定性：穩定
//冒泡排序
//相鄰兩位交換，12交換，23交換，34交換，把最大的數放到最右邊
//利用flag標記可以避免無效回圈
func BubbleSort(arr []int) {
length := len(arr)
//length是最后一位，i < length-1，查詢到倒數第二位
for i := 0; i < length-1; i++ {
//true表示此次回圈沒有發生交換
flag := true
//每次回圈j都從0開始，然后j++
//每次回圈最大的數都會被放到最右邊，j的查詢范圍在逐漸減小，所以j < length-1-i
for j := 0; j < length-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
//false表示此次回圈發生了交換
flag = false
}
}
//true表示序列已經有序，直接退出，不用繼續回圈
//false表示本次回圈發生了交換，需要繼續判斷下個回圈
if flag {
break
}
}
}
簡單選擇排序：
時間復雜度：O(n^2)
穩定性：不穩定
//簡單選擇排序
//回圈一遍，把最小的放最左邊；回圈剩下的序列
//回圈時只取值比較，一遍回圈完發生交換
func selectSort(arr []int) {
length := len(arr)
for i := 0; i < length; i++ {
//從首位i開始，最小指向i，依次與后面比較
min := i
for j := i + 1; j < length; j++ {
//j比首位小，把最小指向j
if arr[min] > arr[j] {
min = j
}
}
//回圈完一遍，最小值發生過變化
if min != i {
//交換i和min
arr[i], arr[min] = arr[min], arr[i]
}
}
}
直接插入排序：
時間復雜度：O(n^2)
穩定性：穩定
//直接插入排序
//取首元素作為有序佇列，把第二位插入到有序佇列中，把第三位插入到前兩位組成的有序佇列中
//新的一位插入有序佇列時，跟他的前一位比較，即有序佇列的最右邊，依次向前遍歷
func insertSort(arr []int) {
length := len(arr)
//從第二位開始處理，所以i從1開始
for i := 1; i < length; i++ {
//if滿足，則新的一位需要插入處理；else表示新的一位依舊有序，不處理
if arr[i] < arr[i-1] {
//arr[i]插入時，前面的元素需要后移，i位置元素被頂掉，所以需要臨時存值
temp := arr[i]
//j取有序佇列的最右位i-1，依次向左j--
j := i - 1
//temp < arr[j]，把j向后移位，依次回圈，直到temp >= arr[j]
for ; j >= 0 && temp < arr[j]; j-- {
//把j向后移位
arr[j+1] = arr[j]
}
//因為發生了j--
arr[j+1] = temp
}
}
}
希爾排序：
時間復雜度：O(n^1.5)
穩定性：不穩定
//希爾排序
//按間隔分組，每組進行插入排序
//長度為10，間隔為10/2=5，按(0,5)(1,6)(2,7)(3,8)(4,9)分組
//間隔減小為5/2=2，按(0,2,4,6,8)(1,3,5,7,9)分組
//組內插入排序時，各組之間交替比較，以間隔為2舉例：先比較0和2，再比較1和3，再比較4，再比較5，依次遍歷
//直到間隔為1，按(0,1...9)分組
func shellSsort(arr []int) {
length := len(arr)
//按間隔分組
for gap := length / 2; gap > 0; gap /= 2 {
//當前各個分組進行插入排序
for i := gap; i < length; i++ {
if arr[i] < arr[i-gap] {
temp := arr[i]
j := i - gap
for ; j >= 0 && temp < arr[j]; j -= gap {
arr[j+gap] = arr[j]
}
arr[j+gap] = temp
}
}
}
}
歸并排序：
時間復雜度：O(nlogn)
穩定性：穩定
//歸并排序
//將兩個有序序列合并成一個有序序列
//取中間值分左右遞回處理
func mergeSort(r []int) []int {
length := len(r)
if length <= 1 {
return r
}
//左右分別處理
num := length / 2
left := mergeSort(r[:num])
right := mergeSort(r[num:])
//左右兩邊都為有序，進行合并
return merge(left, right)
}
func merge(left, right []int) (result []int) {
l, r := 0, 0
//left或right有一方遍歷完則退出回圈
for l < len(left) && r < len(right) {
if left[l] < right[r] {
result = append(result, left[l])
l++
} else {
result = append(result, right[r])
r++
}
}
//left和right均為有序，直接將剩余部分加進序列
//如果上面是left遍歷完，left[l:]為[]，right還有剩余值
//如果上面是right遍歷完，right[r:]為[], left還有剩余值
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}
快速排序：
時間復雜度：O(nlogn)
穩定性：不穩定
//快速排序
//取首位元素為臨界值，一遍回圈，臨界值左邊為小數，右邊為大數
//遞回臨界值左邊和右邊
func quickSort(arr []int) {
length := len(arr)
if length <= 1 {
return
}
quick(arr, 0, length-1)
}
func quick(arr []int, start, end int) {
if start >= end {
return
}
i, j := start, end
//取首位元素為分界值
temp := arr[i]
for i < j {
//從右往左找，大的不處理，j--
for i < j && arr[j] >= temp {
j--
}
//直到遇見第一個小的，跳出上面回圈
if i < j {
//把小的給i，temp的值沒發生變化
arr[i] = arr[j]
i++
}
//從左往右找，小的不處理，i++
for i < j && arr[i] <= temp {
i++
}
//直到遇見第一個大的，跳出上面回圈
if i < j {
//把大的給j，temp的值沒發生變化
arr[j] = arr[i]
j--
}
}
//把temp給到i位置
arr[i] = temp
//遞回i的左邊，0到i-1
quick(arr, start, i-1)
//遞回i的右邊，i+1到right
quick(arr, i+1, end)
}
堆排序：
時間復雜度：O(nlogn)
穩定性：不穩定
//堆排序
//升序使用大頂堆，降序使用小頂堆，以大頂堆為例
//頂堆是上下比較大小，父結點與其孩子比較，同一父結點的左右大小無限制，二叉搜索樹是左右比較大小，不要搞混
//先調整序列為大頂堆(序列默認是一棵二叉樹，把該二叉樹調整為大頂堆)
//處理大頂堆：首尾交換，末位最大，去掉末位，調整剩下序列為大頂堆，回圈處理
func heapSort(arr []int) []int {
length := len(arr)
//調整序列為大頂堆
for i := length/2 - 1; i >= 0; i-- {
//從最后一個非葉子結點開始，從右往左，從下往上，length/2-1為最后一個非葉子結點
adjustHeap(arr, i, length)
}
//處理大頂堆
//大頂堆左右無序，上下有序
for i := length - 1; i > 0; i-- {
//首位最大，首尾交換，把最大放在隊尾
arr[0], arr[i] = arr[i], arr[0]
//去掉隊尾最大元素，所以佇列長度length-1，即為i，把剩余i個元素調整為大頂堆
//此時只有剛交換的首位不符合大頂堆條件，沒必要像上面回圈所有非葉子結點，只需從首位開始調整，所以i=0
adjustHeap(arr, 0, i)
}
return arr
}
//調整二叉樹為大頂堆
func adjustHeap(arr []int, i, length int) {
//非葉子結點i的左右孩子
left := 2*i + 1
right := 2*i + 2
//默認i為最大
max := i
//存在左孩子且左孩子大，最大指向left，因為右孩子可能更大，所以暫不交換
if left < length && arr[left] > arr[max] {
max = left
}
//存在右孩子且右孩子更大，最大指向right
if right < length && arr[right] > arr[max] {
max = right
}
//最大發生過改變，交換
if max != i {
arr[i], arr[max] = arr[max], arr[i]
//最后一層非葉子結點，遞回時不發生交換操作；
//假如二叉樹深度為4，最后一層非葉子結點為第三層，處理第二層發生交換時，需要遞回處理第三層是否被影響了
adjustHeap(arr, max, length)
}
}
基數排序：
時間復雜度：O(d(n+r))
穩定性：穩定
//基數排序
//分配式排序，桶子法，非負數，共0-9，10個桶子
//首次回圈根據元素個位數，將元素分配至對應桶子里，0進0號桶，9進9號桶
//按桶子排序，再次回圈，根據元素十位數再次分配
func radixSort(arr []int) {
length := len(arr)
if length <= 1 {
return
}
//元素的最大位數
d := maxBit(arr)
//用mod和dev求對應位數上的數值
mod, dev := 10, 1
//回圈位數
for i := 0; i < d; i++ {
//10個桶子
temp := [10][]int{}
//遍歷序列
for j := 0; j < length; j++ {
//先求余，再求商
//個位數值：x%10/1；十位數值：x%100/10
bucket := arr[j] % mod / dev
//按位存值
temp[bucket] = append(temp[bucket], arr[j])
}
//為arr排序時的下標
k := 0
//排序arr
for m := 0; m < 10; m++ {
for n := 0; n < len(temp[m]); n++ {
arr[k] = temp[m][n]
k++
}
}
//為下一位做準備
mod *= 10
dev *= 10
}
}
//基數排序
//分配式排序，桶子法，存在負數，共0-19，20個桶子
//首次回圈根據元素個位數，將元素分配至對應桶子里，-9進1號桶，-1進9號桶，0進10號桶，1進11號桶，19進19號桶
//按桶子排序，再次回圈，根據元素十位數再次分配
func radixSort(arr []int) {
length := len(arr)
if length <= 1 {
return
}
//元素的最大位數
d := maxBit(arr)
//用mod和dev求對應位數上的數值
mod, dev := 10, 1
//回圈位數
for i := 0; i < d; i++ {
//10個桶子
temp := [20][]int{}
//遍歷序列
for j := 0; j < length; j++ {
//先求余，再求商，下標不為負，+10保證為非負數
//個位數值：x%10/1+10；十位數值：x%100/10+10
bucket := (arr[j] % mod / dev)+10
//按位存值
temp[bucket] = append(temp[bucket], arr[j])
}
//為arr排序時的下標
k := 0
//排序arr
for m := 0; m < 20; m++ {
for n := 0; n < len(temp[m]); n++ {
arr[k] = temp[m][n]
k++
}
}
//為下一位做準備
mod *= 10
dev *= 10
}
}
//元素的最大位數
func maxBit(arr []int) int {
length := len(arr)
d := 1
p := 10
for i := 0; i < length; i++ {
for arr[i] >= p {
d++
p *= 10
}
}
return d
}
公眾號：李田路口
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/53023.html
標籤：Go
上一篇：洗掉單鏈表，你會嗎？
下一篇：Go語言底層知識總結【新手必學】