Go 排序算法探祕：打造通用 qsort 函數

概述

快速排序（QuickSort）是一種經典的排序算法，其高效性和廣泛應用使之成爲計算機科學領域的瑰寶。

本文將介紹如何在 Go 語言中封裝快速排序函數，使其更易用、更具通用性，並通過示例和代碼解釋，讓讀者深入瞭解其原理和實現。

1. 快速排序算法簡介

1.1 算法原理

快速排序是一種分治策略的排序算法，基本思想是通過選定一個基準元素。

將序列分爲兩部分，小於基準的元素放在左邊，大於基準的元素放在右邊，然後對左右子序列遞歸地進行快速排序。

1.2 示例代碼

package main
import "fmt"
func quickSort(arr []int) {
  if len(arr) <= 1 {
    return
  }
  pivotIndex := partition(arr)
  quickSort(arr[:pivotIndex])
  quickSort(arr[pivotIndex+1:])
}
func partition(arr []int) int {
  pivot := arr[0]
  left, right := 1, len(arr)-1
  for left <= right {
    for left <= right && arr[left] < pivot {
      left++
    }
    for left <= right && arr[right] > pivot {
      right--
    }
    if left <= right {
      arr[left], arr[right] = arr[right], arr[left]
      left++
      right--
    }
  }
  arr[0], arr[right] = arr[right], arr[0]
  return right
}
func main() {
  arr := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
  quickSort(arr)
  fmt.Println("Sorted array:", arr)
}

在這個示例代碼中，quickSort 函數實現了快速排序的遞歸調用，而 partition 函數負責在每一輪排序中選擇基準元素，並對數組進行分割。

2. 封裝快速排序函數

2.1 設計思路

爲了使快速排序更易用和通用，將其封裝爲一個獨立的函數，並提供參數來支持不同類型的切片排序。

2.2 示例代碼

package main
import (
  "fmt"
  "reflect"
)
func QuickSort(slice interface{}) {
  value := reflect.ValueOf(slice)
  if value.Kind() != reflect.Slice {
    panic("Input is not a slice")
  }
  quickSortGeneric(slice, 0, value.Len()-1)
}
func quickSortGeneric(slice interface{}, low, high int) {
  value := reflect.ValueOf(slice)
  if low < high {
    pivotIndex := partitionGeneric(slice, low, high)
    quickSortGeneric(slice, low, pivotIndex-1)
    quickSortGeneric(slice, pivotIndex+1, high)
  }
}
func partitionGeneric(slice interface{}, low, high int) int {
  value := reflect.ValueOf(slice)
  pivot := value.Index(low).Interface()
  left, right := low+1, high
  for left <= right {
    for left <= right && reflect.ValueOf(slice).Index(left).Interface() < pivot {
      left++
    }
    for left <= right && reflect.ValueOf(slice).Index(right).Interface() > pivot {
      right--
    }
    if left <= right {
      swap(slice, left, right)
      left++
      right--
    }
  }
  swap(slice, low, right)
  return right
}
func swap(slice interface{}, i, j int) {
  value := reflect.ValueOf(slice)
  tmp := value.Index(i).Interface()
  value.Index(i).Set(value.Index(j))
  value.Index(j).Set(reflect.ValueOf(tmp))
}
func main() {
  arr := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
  QuickSort(arr)
  fmt.Println("Sorted array:", arr)
  strArr := []string{"banana", "apple", "orange", "grape"}
  QuickSort(strArr)
  fmt.Println("Sorted strings:", strArr)
}

在這個示例中，QuickSort 函數接受任意類型的切片，並使用反射進行排序。

提供不同類型的切片，展示瞭如何通過該通用函數對整數和字符串切片進行排序。

3. 小結

通過本文的介紹，讀者應該對快速排序算法有了更深刻的理解，並學會如何在 Go 語言中封裝一個通用的快速排序函數。

這種封裝提高了代碼的可複用性，使得可以輕鬆地在不同類型的數據上使用相同的排序算法。

在實際開發中，更靈活的排序函數能夠爲程序員提供更多的選擇，使得排序過程更加便捷和高效。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/L0Tu4UyR87GtR2w6g6RW6Q