Go: 八大常用排序算法
1. 選擇排序
原理
每次選擇數組中的最小元素，排在最新的第一個位置
算法步驟
[38,65,97,76,13,27,49]
13 [65 97 76 38 27 49]
13 27 [97 76 38 65 49]
13 27 38 [76 97 65 49]
13 27 38 49 [97 65 76]
13 27 38 49 65 [97 76]
13 27 38 49 65 76 [97]
13 27 38 49 65 76 97
代碼實現
func SelectSort(data []int) {
length := len(data)
for i := 0; i < length; i++ {
// 記錄第一個數據
min := data[i]
index := i
// 獲取到最小的值以及對應的索引
for j := i + 1; j < length; j++ {
if min > data[j] {
min = data[j]
index = j
}
}
// 如果最小的值不是當前序列的第一個值
// 那麼需要進行交換
if index != i {
// 交換最小值
data[index], data[i] = data[i], min
}
}
}
2. 插入排序
原理
假設之前的數組都是一個有序序列，其餘的記錄爲無序序列，從這些無序序列中不斷選取數據，插入到前面已經排序好的有序序列中
算法步驟
[38] 65 97 76 13 27 49
[38 65] 97 76 13 27 49
[38 65 97] 76 13 27 49
[38 65 76 97] 13 27 49
[13 38 65 76 97] 27 49
[13 27 38 65 76 97] 49
[13 27 38 49 65 76 97]
代碼實現
func InsertSort(data []int) {
for i := 1; i < len(data); i++ {
tmp, j := data[i], i
// 如果第j-1個元素比第i個元素大
// 不滿足遞增的條件，第i個需要移動到前面
if data[j-1] > tmp {
// 將第i個元素移動到前面的適當位置
// 也就是將元素不斷的向右邊移動，直到找到合適的位置擺放
for j >= 1 && data[j-1] > tmp {
data[j] = data[j-1]
j--
}
}
// 將當前遍歷到的值填充到對應的位置
data[j] = tmp
}
}
3. 冒泡排序
原理
基本思路: 從第一個元素開始一次對相鄰的記錄進行比較， 當前面的記錄大於後面的記錄，交換其位置，進行一輪比較和換位之後，n 個記錄中的最大記錄將位於第 n 位
算法步驟
{38 65 97 76 13 27 49}
38 65 76 13 27 49 [97]
38 65 13 27 49 [76 97]
38 13 27 49 [65 76 97]
13 27 38 [49 65 76 97]
13 27 [38 49 65 76 97]
13 [27 38 49 65 76 97]
[13 27 38 49 65 76 97]
代碼實現
func BubbleSort(nums []int) {
flag := false
n := len(nums)
// 這裏採用的是不斷將最大的移動到數組的最後面
// 當然也可以將最小的移動到最前面來
for i := 0; i < n ; i ++{
for j := 0; j < n-1 -i; j ++{
if nums[j] > nums[j+1]{
nums[j], nums[j+1] = nums[j+1], nums[j]
flag = true
}
}
if !flag{
break
}
fmt.Println(nums)
}
}
4. 歸併排序
原理
將一個數組拆成兩份，每一份進行遞歸操作之後都是有序的，然後進行合併，最終是有序的。
算法步驟
{38 65 97 76 13 27 49}
[38 65 97 76] [13 27 49]
[38 65] [97 76] [13 27] [49]
[38] [65] [97] [76] [13] [27] [49] // 全部分裂
[38 65] [76 97] [13 27] [49] // 開始進行合併
[38 65 76 97] [13 27 49]
[13 27 38 49 65 76 97]
代碼實現
func MergerSort(nums []int) {
mergeSort(nums, 0, len(nums)-1)
}
func mergeSort(nums []int, left, right int) {
if left >= right {
return
}
mid := (right-left)/2 + left
mergeSort(nums, left, mid)
mergeSort(nums, mid+1, right)
merge(nums, left, mid, right)
}
// 合併兩個數組，分別是從 left -> mid , mid -> right 索引開始
func merge(nums []int, left, mid, right int) {
// 輔助數據
tmp := make([]int, right-left+1)
for i := left; i <= right; i++ {
tmp[i-left] = nums[i]
}
i, j := 0, mid-left+1
k := left
for k <= right && i <= mid-left && j <= right-left {
if tmp[i] > tmp[j] {
nums[k] = tmp[j]
k++
j++
} else {
nums[k] = tmp[i]
i++
k++
}
}
for i <= mid-left {
nums[k] = tmp[i]
i++
k++
}
for j <= right-left {
nums[k] = tmp[j]
j++
k++
}
}
5. 快速排序
快速排序是一種非常高效的排序算法，它採用分而治之的思想，把大的拆分成小的，小的再拆分成更小的。
原理
對於一組給定的記錄，通過一趟排序之後，將原來的序列分成兩部分，其中一部分的所有記錄均比後一部分的所有記錄小，然後再依次對前後兩部分的記錄進行快速排序，遞歸改過程，直到序列中的所有記錄均有序爲止
可以直接認爲是找到了一個分界點，比如如果需要實現遞增，那麼左邊都是小於該數，右邊都是大於該數
算法步驟
-
分解：將輸入的序列
array[m...n]劃分成兩個非空子序列array[m...k]和array[k+1...n]，使得array[k+1...n]中的任意一個元素都不小於array[m...k]中的元素 -
遞歸求解：通過遞歸調用快速排序算法分別對
array[m...k]和array[k+1...n]進行排序 -
合併：由於對分解出來的兩個子序列的排序是就地進行的，所以在
array[m...k]和array[k+1...n]都排好序後不需要執行任何計算array[m...n]
代碼實現
func sort(arr []int, left, right int) {
if left >= right {
return
}
i := left
j := right
// 選定一個分界點
// 如果直接下面這種方式取的話，如果數據是有序的，那麼時間複雜度相比較會比較高
index := arr[i]
// 也可以隨機挑選一個
// rand.Seed(time.Now().UnixNano())
// var random int
// random = rand.Int() % (right-left+1) + left
// 將隨機選中的移動到最左邊
// arr[i], arr[random] = arr[random], arr[i]
// 這裏只是爲了更新上面的index，如果直接寫的話，可以去掉上的賦值，直接使用index:= arr[i]
// index = arr[i]
for i < j {
// 右邊界不斷向左移動，如果碰到比index小的數據
// 則需要將左邊的i對應的數據賦值爲對應的值
for i < j && arr[j] >= index {
j--
}
if i < j {
arr[i] = arr[j]
i++
}
// 左邊界不斷往右移動，如果碰到比index小的數據
// 則將右邊的這個數據賦值索引j對應的數據
for i < j && arr[i] <= index {
i++
}
if i < j {
arr[j] = arr[i]
j--
}
}
// 索引i表示的就是
arr[i] = index
// 排序左邊子數組
sort(arr, left, i-1)
// 排序右邊
sort(arr, i+1, right)
}
func QuickSort(arr []int) {
sort(arr, 0, len(arr)-1)
}
基準關鍵字的選取
常用的基準關鍵字的選取有以下方式:
-
選取首尾，中間位置上的中值作爲基準關鍵字
-
選取隨機數
6. 希爾排序
原理
類似插入排序，但是不是相鄰的進行，而是會跳過幾個位置
算法步驟
{38, 65, 97, 76, 13, 27, 49}
step爲: 3 [38 65 97 76 13 27 49] // 索引 3 和 0 進行比較並交換
step爲: 3 [38 13 97 76 65 27 49] // 索引 4 和 1 進行比較並交換
step爲: 3 [38 13 27 76 65 97 49] // 索引 5 和 2 進行比較並交換
step爲: 3 [38 13 27 49 65 97 76] // 索引 6 和 3 進行比較並交換
step爲: 1 [13 38 27 49 65 97 76] // 索引 1 和 0 進行比較並交換
step爲: 1 [13 27 38 49 65 97 76] // 索引 2 和 1 進行比較並交換
step爲: 1 [13 27 38 49 65 97 76] // 索引 3 和 2 進行比較並交換
step爲: 1 [13 27 38 49 65 97 76] // 索引 4 和 3 進行比較並交換
step爲: 1 [13 27 38 49 65 97 76] // 索引 5 和 4 進行比較並交換
step爲: 1 [13 27 38 49 65 76 97] // 索引 6 和 5 進行比較並交換
代碼實現
func ShellSort(nums []int) {
// 步長
for step := len(nums) / 2; step > 0; step /= 2 {
for i := step ; i < len(nums); i++ {
// 直接插入排序
if nums[i] < nums[i-step] {
j, tmp := i, nums[i]
// 找出同一組中比tmp小的值，往後面移動step個位置
for j >= step && tmp < nums[j-step] {
nums[j] = nums[j-step]
j -= step
}
nums[j] = tmp
}
}
}
}
7. 堆排序
原理
這裏說一下遞增排序，使用大根堆
大根堆有一個特點，那就是堆的頂部是整個數組中最大的元素，一個比較簡單的想法就是，我把這個元素拿出來，然後插入到其他的數組中，堆中 pop 出堆頂的元素，依次進行，便可以獲取到一個排序序列，不過這種思路需要多餘的一個數組，其實沒有必要，我們來自己看看刪除元素的過程。
首先，將堆頂的元素和最後一個元素進行交換，然後 size--，進行向下冒泡 down，刪除掉最後一個元素。
func pop(arr *[]int) int {
nums := *arr
n := len(nums) - 1
// 交換
nums[0], nums[n] = nums[n], nums[0]
down(nums, 0, n)
x := nums[n]
// 刪除最後一個元素
*arr = (*arr)[:n]
return x
}
注意這裏刪除最後一個元素，我們可以把這個元素保留在這裏，但是讓 down 的時候不接觸到這個元素不就行了？這個很好實現，因爲一般我們都是使用元素的長度作爲 down 的一個 size 參數，我們指定一下就好，主要的邏輯代碼如下：
func heapSort(nums []int) {
size := len(nums)
// 首先建堆
buildHeap(nums)
// 然後這個時候最大的元素在第一個
for size > 1 {
// 第一個元素和最後一個進行交換
nums[0], nums[size-1] = nums[size-1], nums[0]
size--
down(nums, 0, size)
}
}
代碼實現
// 建大根堆
func buildHeap(nums []int) {
size := len(nums)
for i := size / 2; i >= 0; i-- {
down(nums, i, size)
}
}
// 插入元素的時候需要使用
func up(nums []int, i int) {
for {
// 父結點計算公式！！
parent := (i - 1) / 2
// 如果父結點大於子節點了，說明不需要調換，已經滿足條件了
// 如果 i == parent 說明 i = 0 了，沒有父結點，也不需要調換
if i == parent || nums[parent] > nums[i] {
break
}
// 父結點沒有子節點i的值大，需要調換
nums[parent], nums[i] = nums[i], nums[parent]
}
}
// 初始化的時候需要建堆
// 刪除元素的時候需要down：
// 將第一個元素和最後一個元素進行調換, 然後重新 down(nums, 0, size)
func down(nums []int, i int, size int) {
left, right := 2*i+1, 2*i+2
j := i
// 找到最大的元素的下標
if left < size && nums[left] > nums[j] {
j = left
}
if right < size && nums[right] > nums[j] {
j = right
}
if j != i {
nums[i], nums[j] = nums[j], nums[i]
down(nums, j, size)
}
}
// 不用遞歸也可以
func down2(nums []int, i, size int) {
for {
left, right := i*2+1, i*2+2
// 說明i是葉子節點
if left >= size {
break
}
// 找到最大的節點
largest := i
if left < size && nums[left] > nums[largest] {
largest = left
}
if right < size && nums[right] > nums[largest] {
largest = right
}
if largest != i {
nums[i], nums[largest] = nums[largest], nums[i]
i = largest
} else {
// 如果最大的節點就是本身，那麼後面也不需要進行操作了
break
}
}
}
// 從堆中彈出一個數
// 首先將堆頂的元素和最後一個元素進行調換，然後進行down操作
func pop(arr *[]int) int {
nums := *arr
n := len(nums) - 1
nums[0], nums[n] = nums[n], nums[0]
down(nums, 0, n)
x := nums[n]
*arr = (*arr)[:n]
return x
}
func HeapSort(nums []int) {
size := len(nums)
// 首先建堆
buildHeap(nums)
// 然後這個時候最大的元素在第一個
for size > 1 {
// 第一個元素和最後一個進行交換
nums[0], nums[size-1] = nums[size-1], nums[0]
size--
down(nums, 0, size)
}
}
8. 計數排序
原理
設置一個長度爲元素最大值最小值的空間，將元素一個一個對應一個索引，如果這個索引中已經存在元素，那麼對應的值 + 1，說明這個索引處對應多個元素，最後遍歷一遍這個索引空間，值爲 0 的不需要添加，值爲多個的一次添加到原數組中
計數排序適合於數組中的值在一定範圍內的數據，比如說年齡，數據可能需要進行整理，比如 [10000, 20000] 的數據，我們可以首先整理爲 [0, 10000]，然後再轉換回去。
代碼實現
// 比如我們需要排序年齡，那麼我們可以估算年齡在[0,200]中
func CountingSort(nums []int) {
count := make([]int, 200)
for _, num := range nums {
count[num] ++
}
index := 0
for i :=0; i < len(count); i ++ {
// 出現了多少次，排序後添加到原數組多少次
for j:= 0; j < count[i]; j++ {
nums[index] = i
index ++
}
}
}
9. 總結
下圖給出了每種排序算法的穩定性和效率的比較：
如果想要更直觀的看排序過程，推薦使用 Data Structure Visualizations[1] 這個網站，進行查看，比如想要看插入排序的，可以選擇 Insertion Sort 即可
鏈接
[1] Data Structure Visualizations: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[2] GitHub: https://github.com/junhaideng/Blog/tree/main/alg/sort
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/dtCaWKuxkA73L3kRLRn-jA