本文介绍: 切片是Go语言引入用于在大多数场合替代数组语法元素切片长度可变的同类型元素序列,它不支持存储不同类型元素有序列的地方就有排序需求。在各种排序算法都已经成熟的今天我们完全可以针对特定元素类型切片手写排序函数/方法,但多数情况下不推荐这么做,因为Go标准内置sort可以很好地帮助我们实现原生类型元素切片以及自定义类型元素切片的排序任务。Gosort用来排序二分查找操作

前言

切片是Go语言中引入用于在大多数场合替代数组语法元素切片是长度可变的同类型元素序列,它不支持存储不同类型元素
序列的地方就有排序需求。在各种排序算法都已经成熟的今天我们完全可以针对特定元素类型的切片手写排序函数/方法,但多数情况下不推荐这么做,因为Go标准内置sort可以很好地帮助我们实现原生类型元素切片以及自定义类型元素切片的排序任务。

一、sort简介

Gosort用来排序,二分查找操作

二、sort包内排序原理实现

type Interface interface {
	// Len是集合中元素的个数
	Len() int
	// Less是排序条件索引i与j的元素对比排序)
	Less(i, j int) bool
	// Swap交换索引i和j的元素。
	Swap(i, j int)
}

// Sort按Less方法确定的升序数据进行排序。
func Sort(data Interface) {
	n := data.Len()
	if n <= 1 {
		return
	}
	limit := bits.Len(uint(n))
	pdqsort(data, 0, n, limit)
}

入口的 Sort 函数调用pdqsort 并不完全是快排。

pdqsort实质为一种混合排序算法,在不同情况下切换不同的排序机制,该实现灵感来自C++和RUST的实现,是对C++标准库算法introsort的一种改进,其理想情况下的时间复杂度为 O(n),最坏情况下的时间复杂度为 O(n* logn),不需要额外空间

pdqsort算法的改进在于对常见的情况做了特殊优化,其主要的思想是不断判定目前的序列情况,然后使用不同方式路径达到最优解;其实现就是对下面三种情况的不断循环

func pdqsort(data Interface, a, b, limit int) {
	const maxInsertion = 12

	var (
		wasBalanced    = true // whether the last partitioning was reasonably balanced
		wasPartitioned = true // whether the slice was already partitioned
	)

	for {
		length := b - a

		if length <= maxInsertion {
			insertionSort(data, a, b)
			return
		}

		// Fall back to heapsort if too many bad choices were made.
		if limit == 0 {
			heapSort(data, a, b)
			return
		}

		// If the last partitioning was imbalanced, we need to breaking patterns.
		if !wasBalanced {
			breakPatterns(data, a, b)
			limit--
		}

		pivot, hint := choosePivot(data, a, b)
		if hint == decreasingHint {
			reverseRange(data, a, b)
			// The chosen pivot was pivot-a elements after the start of the array.
			// After reversing it is pivot-a elements before the end of the array.
			// The idea came from Rust's implementation.
			pivot = (b - 1) - (pivot - a)
			hint = increasingHint
		}

		// The slice is likely already sorted.
		if wasBalanced &amp;&amp; wasPartitioned &amp;&amp; hint == increasingHint {
			if partialInsertionSort(data, a, b) {
				return
			}
		}

		// Probably the slice contains many duplicate elements, partition the slice into
		// elements equal to and elements greater than the pivot.
		if a > 0 &amp;&amp; !data.Less(a-1, pivot) {
			mid := partitionEqual(data, a, b, pivot)
			a = mid
			continue
		}

		mid, alreadyPartitioned := partition(data, a, b, pivot)
		wasPartitioned = alreadyPartitioned

		leftLen, rightLen := mid-a, b-mid
		balanceThreshold := length / 8
		if leftLen < rightLen {
			wasBalanced = leftLen >= balanceThreshold
			pdqsort(data, a, mid, limit)
			a = mid + 1
		} else {
			wasBalanced = rightLen >= balanceThreshold
			pdqsort(data, mid+1, b, limit)
			b = mid
		}
	}
}

为了更方便理解应用排序函数Sort,我们需要让被排序的切片类型实现 sort.Interface接口,以整型切片排序为例

// IntSlice将Interface方法附加到[]int,按递减顺序排序。
type IntSlice []int

func (x IntSlice) Len() int           { return len(x) }
func (x IntSlice) Less(i, j int) bool { return x[i] > x[j] }
func (x IntSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

func main() {
	sl := IntSlice([]int{24, 46, 81, 9, 67, 6, 5, 13})
	fmt.Println(sl) // [24, 46, 81, 9, 67, 6, 5, 13]
	
	// Sort按照less条件排序
	sort.Sort(sl)
	fmt.Println(sl) // [81 67 46 24 13 9 6 5]
}

使用 sort.Sort 函数实现排序后,因为我们没有重写接口的Sort方法,所以默认使用sort包里Sort函数,它使用的是快速排序(quickSort)
我们知道快速排序是在所有数量级为(O(nlogn))的排序算法中其平均性能最好的算法,但在某些情况下其性能却并非最佳。
Go sort包中的quickSort函数也没有严格拘泥于仅使用快排算法,而是快速排序为主,并根据目标状况在特殊条件下选择了其他不同的排序算法,包括堆排序(heapSort)、插入排序(insertionSort)等。

sort.Sort函数不保证排序是稳定的,要想使用稳定排序,需要使用sort.Stable函数。(保证排序的稳定性,相等元素的相对次序不变)

注:稳定排序:假定在待排序的序列中存在多个具有相同值的元素,若经过排序,这些元素的相对次序保持不变,即在原序列中,若r[i]=r[j]且r[i]在r[j]之前,在排序后的序列中,若r[i]仍在r[j]之前,则称这种排序算法是稳定的(stable);否则称为不稳定的。

三、sort包内置函数

如果我们直接使用sort.Sort函数对切片进行排序还是比较繁琐的,所以sort包提供了许多内置函数比如:Ints、Float64s、Strings、Slice,、Sort、 SearchInts、SearchFloat64s、SearchStrings和Search等。

1、sort.Ints(x []int)

	ints := []int{1, 4, 3, 2}
	fmt.Printf("%vn", ints) 
	sort.Ints(ints) //默认升序
	fmt.Printf("%vn", ints) //[1 2 3 4] 
	sort.Sort(sort.Reverse(sort.IntSlice(ints))) //降序排序 
	fmt.Printf("%vn", ints) //[4 3 2 1]

sort.Strings(x []string) sort.Float64s(x []float64)使用方法相同。

2、sort.Slice(x any, less func(i, j int) bool)

Slice函数有个好处,如果传入对象是切片,实现回调函数即可,如果传入对象结构体,也可以自定义排序规则

	slices := []int{1, 1, 4, 5, 1, 4}
	sort.Slice(slices, func(i, j int) bool {
		return slices[i] < slices[j]
	})
	fmt.Printf("%vn", slices)//[1 1 1 4 4 5]
	type stu struct {
		name string
		age  int
	}

	stus := []stu{{"h", 20}, {"a", 23}, {"h", 21}}
	sort.Slice(stus, func(i, j int) bool {
		if stus[i].name == stus[j].name {
			return stus[i].age > stus[j].age // 年龄逆序
		}
		return stus[i].name < stus[j].name // 名字正序
	})
	fmt.Printf("%vn", stus) //[{a 23} {h 21} {h 20}]

3、sort.SearchInts(a []int, x int) int

作用用来二分查找对应值的索引值,索引值从0开始。

	arr := []int{1, 2, 3, 4, 5, 6, 7}
	idx := sort.SearchInts(arr, 4)
	fmt.Printf("%vn", idx) // 3

sort.SearchFloat64s(a []float64, x float64) int sort.SearchStrings(a []string, x string) int 功能同上。

4、sort.Search(n int, f func(int) bool) int

作用自定义二分查找需要自己实现查找条件

arr := []int{1, 2, 3, 4, 5, 6, 7}
	idx := sort.Search(len(arr), func(i int) bool {
		return arr[i] > 4
	})
	fmt.Printf("%vn", idx) //4

原文地址:https://blog.csdn.net/weixin_46618592/article/details/128916888

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_29022.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注