Go语言封装qsort快速排序函数

void qsort(
void* base, size_t num, size_t size,
int (*cmp)(const void*, const void*)
);

#include #include #define DIM(x) (sizeof(x)/sizeof((x)[0]))static int cmp(const void* a, const void* b) { const int* pa = (int*)a; const int* pb = (int*)b; return *pa - *pb;}int main() { int values[] = { 42, 8, 109, 97, 23, 25 }; int i; qsort(values, DIM(values), sizeof(values[0]), cmp); for(i = 0; i 其中 DIM(values) 宏用于计算数组元素的个数， sizeof(values[0]) 用于计算数组元素的大小。cmp 是用于排序时比较两个元素大小的回调函数。为了避免对全局名字空间的污染，我们将 cmp 回调函数定义为仅当前文件内可访问的静态函数。

将 qsort 函数从 Go 包导出

package qsort//typedef int (*qsort_cmp_func_t)(const void* a, const void* b);import "C"import "unsafe"func Sort( base unsafe.Pointer, num, size C.size_t, cmp C.qsort_cmp_func_t,) { C.qsort(base, num, size, cmp)}因为 Go语言的 CGO 语言不好直接表达 C语言的函数类型，因此在 C语言空间将比较函数类型重新定义为一个 qsort_cmp_func_t 类型。

虽然 Sort 函数已经导出了，但是对于 qsort 包之外的用户依然不能直接使用该函数——Sort 函数的参数还包含了虚拟的 C 包提供的类型。 在虚拟的 C 包下的任何名称其实都会被映射为包内的私有名字。比如 C.size_t 会被展开为 _Ctype_size_t，C.qsort_cmp_func_t 类型会被展开为 _Ctype_qsort_cmp_func_t 。

被 CGO 处理后的 Sort 函数的类型如下：

func Sort(
base unsafe.Pointer, num, size _Ctype_size_t,
cmp _Ctype_qsort_cmp_func_t,
)

/*#include typedef int (*qsort_cmp_func_t)(const void* a, const void* b);*/import "C"import "unsafe"type CompareFunc C.qsort_cmp_func_tfunc Sort(base unsafe.Pointer, num, size int, cmp CompareFunc) { C.qsort(base, C.size_t(num), C.size_t(size), C.qsort_cmp_func_t(cmp))}我们将虚拟 C 包中的类型通过 Go语言类型代替，在内部调用 C 函数时重新转型为 C 函数需要的类型。因此外部用户将不再依赖 qsort 包内的虚拟 C 包。

以下代码展示了 Sort 函数的使用方式：

package main//extern int go_qsort_compare(void* a, void* b);import "C"import ( "fmt" "unsafe" qsort ".")//export go_qsort_comparefunc go_qsort_compare(a, b unsafe.Pointer) C.int { pa, pb := (*C.int)(a), (*C.int)(b) return C.int(*pa - *pb)}func main() { values := []int32{42, 9, 101, 95, 27, 25} qsort.Sort(unsafe.Pointer(&values[0]), len(values), int(unsafe.Sizeof(values[0])), qsort.CompareFunc(C.go_qsort_compare), ) fmt.Println(values)}为了使用 Sort 函数，我们需要将 Go语言的切片取首地址、元素个数、元素大小等信息作为调用参数，同时还需要提供一个 C语言规格的比较函数。其中 go_qsort_compare 是用 Go语言实现的，并导出到 C语言空间的函数，用于 qsort 排序时的比较函数。

目前已经实现了对 C语言的 qsort 初步包装，并且可以通过包的方式被其它用户使用。但是 qsort.Sort 函数已经有很多不便使用之处：用户要提供 C语言的比较函数，这对许多 Go语言用户是一个挑战。

下一步我们将继续改进 qsort 函数的包装函数，尝试通过闭包函数代替 C语言的比较函数。消除用户对 CGO 代码的直接依赖。

改进：闭包函数作为比较函数

func Slice(slice interface{}, less func(i, j int) bool)

import "sort"func main() { values := []int32{42, 9, 101, 95, 27, 25} sort.Slice(values, func(i, j int) bool { return values[i] 我们也尝试将 C语言的 qsort 函数包装为以下格式的 Go语言函数：

package qsort
func Sort(base unsafe.Pointer, num, size int, cmp func(a, b unsafe.Pointer) int)

var go_qsort_compare_info struct { fn func(a, b unsafe.Pointer) int sync.Mutex}//export _cgo_qsort_comparefunc _cgo_qsort_compare(a, b unsafe.Pointer) C.int { return C.int(go_qsort_compare_info.fn(a, b))}其中导出的 C语言函数 _cgo_qsort_compare 是公用的 qsort 比较函数，内部通过 go_qsort_compare_info.fn 来调用当前的闭包比较函数。

新的 Sort 包装函数实现如下：

/*#include typedef int (*qsort_cmp_func_t)(const void* a, const void* b);extern int _cgo_qsort_compare(void* a, void* b);*/import "C"func Sort(base unsafe.Pointer, num, size int, cmp func(a, b unsafe.Pointer) int) { go_qsort_compare_info.Lock() defer go_qsort_compare_info.Unlock() go_qsort_compare_info.fn = cmp C.qsort(base, C.size_t(num), C.size_t(size), C.qsort_cmp_func_t(C._cgo_qsort_compare), )}每次排序前，对全局的 go_qsort_compare_info 变量加锁，同时将当前的闭包函数保存到全局变量，然后调用 C语言的 qsort 函数。

基于新包装的函数，我们可以简化之前的排序代码：

func main() { values := []int32{42, 9, 101, 95, 27, 25} qsort.Sort(unsafe.Pointer(&values[0]), len(values), int(unsafe.Sizeof(values[0])), func(a, b unsafe.Pointer) int { pa, pb := (*int32)(a), (*int32)(b) return int(*pa - *pb) }, ) fmt.Println(values)}现在排序不再需要通过 CGO 实现 C语言版本的比较函数了，可以传入 Go语言闭包函数作为比较函数。但是导入的排序函数依然依赖 unsafe 包，这是违背 Go语言编程习惯的。

改进：消除用户对 unsafe 包的依赖

package qsort
func Slice(slice interface{}, less func(a, b int) bool)

var go_qsort_compare_info struct {
base unsafe.Pointer
elemnum int
elemsize int
less func(a, b int) bool
sync.Mutex
}

//export _cgo_qsort_comparefunc _cgo_qsort_compare(a, b unsafe.Pointer) C.int { var ( // array memory is locked base = uintptr(go_qsort_compare_info.base) elemsize = uintptr(go_qsort_compare_info.elemsize) ) i := int((uintptr(a) - base) / elemsize) j := int((uintptr(b) - base) / elemsize) switch { case go_qsort_compare_info.less(i, j): // v[i] v[j] return +1 default: return 0 }}新的 Slice 函数的实现如下：

func Slice(slice interface{}, less func(a, b int) bool) { sv := reflect.ValueOf(slice) if sv.Kind() != reflect.Slice { panic(fmt.Sprintf("qsort called with non-slice value of type %T", slice)) } if sv.Len() == 0 { return } go_qsort_compare_info.Lock() defer go_qsort_compare_info.Unlock() defer func() { go_qsort_compare_info.base = nil go_qsort_compare_info.elemnum = 0 go_qsort_compare_info.elemsize = 0 go_qsort_compare_info.less = nil }() // baseMem = unsafe.Pointer(sv.Index(0).Addr().Pointer()) // baseMem maybe moved, so must saved after call C.fn go_qsort_compare_info.base = unsafe.Pointer(sv.Index(0).Addr().Pointer()) go_qsort_compare_info.elemnum = sv.Len() go_qsort_compare_info.elemsize = int(sv.Type().Elem().Size()) go_qsort_compare_info.less = less C.qsort( go_qsort_compare_info.base, C.size_t(go_qsort_compare_info.elemnum), C.size_t(go_qsort_compare_info.elemsize), C.qsort_cmp_func_t(C._cgo_qsort_compare), )}首先需要判断传入的接口类型必须是切片类型。然后通过反射获取 qsort 函数需要的切片信息，并调用 C语言的 qsort 函数。

基于新包装的函数我们可以采用和标准库相似的方式排序切片：

import ( "fmt" qsort ".")func main() { values := []int64{42, 9, 101, 95, 27, 25} qsort.Slice(values, func(i, j int) bool { return values[i] 为了避免在排序过程中，排序数组的上下文信息 go_qsort_compare_info 被修改，我们进行了全局加锁。因此目前版本的 qsort.Slice 函数是无法并发执行的，读者可以自己尝试改进这个限制。

好了，本文到此结束，带大家了解了《Go语言封装qsort快速排序函数》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多Golang知识！