Golang實現常見排序演演算法的範例程式碼

2022-05-17 19:01:23

前言

現在的面試真的是越來越捲了，演演算法已經成為了面試過程中必不可少的一個環節，你如果想進稍微好一點的公司，「演演算法是必不可少的一個環節」。那麼如何學習演演算法呢?很多同學的第一反應肯定是去letcode上刷題，首先我並不反對刷題的方式，但是對於一個沒有專門學習過演演算法的同學來說，刷題大部分是沒什麼思路的，花一個多小時暴力破解一道題意義也不大，事後看看別人比較好的解法大概率也記不住，所以我覺得「專門針對演演算法進行一些簡單的訓練」是很有必要的，正好我自己最近也在學習，同時把學習成果同步更新在公眾號上，可能會更很多期，希望能幫助到你。另外最近很多同學也都在學習go，所以我就用go程式碼演示演演算法。今天咱們閒話不用多說，就從最簡單的開始。

五種基礎排序演演算法對比

1、氣泡排序

演演算法描述

比較相鄰的元素。如果第一個比第二個大，就交換它們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
重複步驟1~3，直到排序完成。

程式碼演示

func bubbleSort(arr []int) []int {
 if len(arr) <= 1 {
  return arr
 }
 for e := len(arr) - 1; e > 0; e-- {
  for i := 0; i < e; i++ {
   if arr[i] > arr[i+1] {
    Swap(arr, i, i+1)  //交換元素
   }
  }
 }
 return arr
}
func Swap(arr []int, i, j int) []int {
 temp := arr[j]
 arr[j] = arr[i]
 arr[i] = temp
 return arr
}

2、選擇排序

演演算法描述

n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體演演算法描述如下：

將假想牆放置在數位列表最左側，牆的左側為已排序子列表，右側為未排序子列表。
找出(選擇)未排序子列表中的最小(或最大)元素。
把選擇的元素與未排序列表中第一個元素進行交換。
將假想牆向右移動一個位置。
反覆執行 2 至 4 步操作，直至整個數位列表排序完成(需要 n - 1 輪)。

程式碼演示

func selectSort(arr []int) []int {
 if len(arr) <= 1 {
  return arr
 }
 for i := 0; i < len(arr); i++ {
  var minIndex int = i
  for j := i + 1; j < len(arr); j++ {
   if arr[j] < arr[minIndex] {
    minIndex = j
   }
  }
  arr = Swap(arr, i, minIndex)
 }
 return arr

}
func Swap(arr []int, i, j int) []int {
 temp := arr[j]
 arr[j] = arr[i]
 arr[i] = temp
 return arr
}

3、插入排序

演演算法描述

一般來說，插入排序都採用in-place在陣列上實現。具體演演算法描述如下：

從第一個元素開始，該元素可以認為已經被排序。
取出下一個元素，在已經排序的元素序列中從後向前掃描。
如果該元素(已排序)大於新元素，將該元素移到下一位置。
重複步驟3，直到找到已排序的元素小於或者等於新元素的位置;將新元素插入到該位置後;
重複步驟2~5。

程式碼實現

func insertSort(arr []int) []int {
 if len(arr) <= 1 {
  return arr
 }
 for i := 1; i < len(arr); i++ {
  for j := i - 1; j >= 0; j-- {
   if arr[j] > arr[j+1] {
    Swap(arr, j, j+1)
   }
  }
 }
 return arr
}
func Swap(arr []int, i, j int) []int {
 temp := arr[j]
 arr[j] = arr[i]
 arr[i] = temp
 return arr
}

4、快速排序

演演算法描述

快速排序的基本思想：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

從數列中挑出一個元素，稱為 “基準”(pivot)。
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分割區退出之後，該基準就處於數列的中間位置。這個稱為分割區(partition)操作。
遞迴地(recursive)把小於基準值元素的子數列和大於基準值元素的子數列排序。

程式碼實現

//快速排序
func quickSort(arr []int) []int {
 if len(arr) <= 1 {
  return arr
 }
 middle := arr[0]
 var left []int
 var right []int
 for i := 1; i < len(arr); i++ {
  if arr[i] > middle {
   right = append(right, arr[i])
  } else {
   left = append(left, arr[i])
  }
 }
 middle_s := []int{middle}
 left = quickSort(left)
 right = quickSort(right)
 arr = append(append(left, middle_s...), right...)
 return arr
}

以上就是Golang實現常見排序演演算法的範例程式碼的詳細內容，更多關於Golang排序演演算法的資料請關注it145.com其它相關文章！

Golang實現常見排序演演算法的範例程式碼

目錄

前言

五種基礎排序演演算法對比

1、氣泡排序

2、選擇排序

3、插入排序

4、快速排序

熱門文章