Go는 강력한 형식의 언어이며 코드가 간결하고 읽기 쉽고 효율적인 성능을 제공하므로 개발자들 사이에서 점점 더 인기를 얻고 있습니다. 그중 정렬 패키지는 Go 언어 표준 라이브러리의 중요한 부분으로, 슬라이스 및 사용자 정의 컬렉션 유형에 대한 정렬 기능을 제공합니다. 이 기사에서는 Go 언어로 정렬 패키지를 구현하는 방법을 소개합니다.
sort 패키지의 sort.Interface 인터페이스 정의는 다음과 같습니다.
type Interface interface {
// 嵌入内置的len函数，返回集合元素个数
Len() int
// 比较索引i和索引j上的元素
Less(i, j int) bool
// 交换索引i和索引j上的元素
Swap(i, j int)
}이 인터페이스를 통해 사용자 정의 유형의 정렬 알고리즘을 구현할 수 있습니다.
sort 패키지에는 Sort, Stable, Slice의 세 가지 주요 정렬 방법이 구현되어 있는데, 아래에서 하나씩 소개하겠습니다.
Sort 방법은 들어오는 조각을 정렬하고 최적화된 빠른 정렬 알고리즘을 사용합니다. 소스 코드에서 볼 수 있습니다. 슬라이스 유형은 []Type이므로 Type 슬라이스를 사용하여 Sort 메서드를 직접 호출할 수 있습니다(Type은 슬라이스의 내부 요소 유형입니다).
func Sort(data Interface) {
n := data.Len()
quickSortFunc(n, swapFunc(data), maxDepth(n))
}Sort 메서드는 내부적으로 QuickSortFunc 함수를 호출하여 정렬 작업을 수행합니다. 이 함수는 재귀가 완료되거나 분할된 하위 슬라이스가 너무 작을 때까지 자체적으로 호출됩니다.
// 快速排序
// n 为切片大小
// swap 为交换函数，可以通过sort.Interface中的swap方法来实现
func quickSortFunc(n int, swap swapFunc, maxDepth int) {
// 插入排序，Num^1为偶数，&1可用来判断奇偶性
if n < insertionSortThreshold {
for i := 1; i < n; i++ {
for j := i; j > 0 && swap(j-1, j); j-- {
}
}
return
}
if maxDepth == 0 {
heapSortFunc(n, swap)
return
}
maxDepth--
third := n / 2
// 选择枢纽元
if n > med3Threshold {
m0 := 0
m1 := n / 2
m2 := n - 1
if n > 40 {
s := n / 8
m0 = med3(swap, 0, s, 2*s)
m1 = med3(swap, m1-s, m1, m1+s)
m2 = med3(swap, n-1-2*s, n-1-s, n-1)
}
third = med3(swap, m0, m1, m2)
}
// 挖洞填数
// z正反代表着大或小于枢纽元素
z := n - 1
// p代表在枢纽元素左边的指针，q代表在枢纽元素右边的指针
p := 0
q := z
for {
for ; p < n && !swap(p, third); p++ {
}
for ; q >= 0 && swap(q, third); q-- {
}
if p >= q {
break
}
swap(p, q)
if p == third {
third = q
} else if q == third {
third = p
}
p++
q--
}
// 对子切片递归调用quickSortFunc函数
quickSortFunc(p, swap, maxDepth)
quickSortFunc(n-p-1, swapFuncAt(swap, p+1), maxDepth)
}Stable 방법은 동일한 요소의 상대적 위치를 변경하지 않고 유지할 수 있는 안정적인 정렬 알고리즘입니다. 이 작업은 주로 그림의 요소를 반정렬하는 것과 같이 Sort 메서드의 정렬 규칙을 따르지 않는 일부 조각을 비교적 순서대로 정렬하는 데 사용됩니다.
func Stable(data Interface) {
// length 为切片长度
length := data.Len()
// mergeSort函数就是归并排序
mergeSort(data, 0, length)
}이 알고리즘은 매우 효율적입니다. 안정적인 정렬 알고리즘일 뿐만 아니라 O(n log n)의 복잡성도 있습니다.
Slice는 하위 슬라이스를 정렬합니다. 즉, 슬라이스(시작, 끝)를 정렬하는 데 이 방법을 사용하여 슬라이스에서 지원하는 모든 반복자를 정렬할 수 있습니다.
func Slice(slice interface{}, less func(i, j int) bool) {
// 利用反射获取slice值信息
rv := reflect.ValueOf(slice)
// 获取长度信息
vlen := rv.Len()
// 初始化并调用SortInterface，参数为lessSlice
reflect.Sort(newSortInterface(rv, makeLessSlice(less, vlen)))
}less 함수 메서드의 구현은 sort.Interface의 Less 메서드에 따라 구현되어야 한다는 점에 유의해야 합니다. less 함수는 두 개의 인덱스 i와 j를 전달하고 부울 값을 반환합니다. 요소 i가 만약 그렇다면, swap(i, j).
위는 Go 언어로 정렬 패키지를 간략하게 구현한 것입니다. 위의 소개에서 정렬 패키지는 구현이 비교적 간단하지만 효율적인 정렬 성능을 가지며 개발자에게 큰 편의성을 제공한다는 것을 알 수 있습니다.
위 내용은 Go 언어로 정렬 패키지를 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
