Golang怎么實(shí)現(xiàn)常見排序算法

這篇文章主要介紹“Golang怎么實(shí)現(xiàn)常見排序算法”的相關(guān)知識，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“Golang怎么實(shí)現(xiàn)常見排序算法”文章能幫助大家解決問題。

五種基礎(chǔ)排序算法對比

五種基礎(chǔ)排序算法對比

1、冒泡排序

算法描述

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個。

• 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)。

• 針對所有的元素重復(fù)以上的步驟，除了最后一個。

• 重復(fù)步驟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個記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：

• 將假想墻放置在數(shù)字列表最左側(cè)，墻的左側(cè)為已排序子列表，右側(cè)為未排序子列表。

• 找出(選擇)未排序子列表中的最小(或最大)元素。

• 把選擇的元素與未排序列表中第一個元素進(jìn)行交換。

• 將假想墻向右移動一個位置。

• 反復(fù)執(zhí)行 2 至 4 步操作，直至整個數(shù)字列表排序完成(需要 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在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：

• 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序。

• 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描。

• 如果該元素(已排序)大于新元素，將該元素移到下一位置。

• 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置;將新元素插入到該位置后;

• 重復(fù)步驟2~5。

代碼實(shí)現(xiàn)

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、快速排序

算法描述

快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。

• 從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”(pivot)。

• 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)(partition)操作。

• 遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

代碼實(shí)現(xiàn)

//快速排序
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
}

關(guān)于“Golang怎么實(shí)現(xiàn)常見排序算法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點(diǎn)。