Sắp xếp slice Golang: slices.Sort, SortFunc và nhiều trường

Sắp xếp các kiểu có sẵn

slices.Sort sắp xếp mọi slice có kiểu phần tử có thứ tự: số nguyên, số thực và chuỗi. Hàm sắp xếp tại chỗ và không trả về gì.

package main

import (
	"fmt"
	"slices"
)

func main() {
	nums := []int{42, 7, 19, 3, 88}
	slices.Sort(nums)
	fmt.Println(nums)

	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.Sort(names)
	fmt.Println(names) // byte order: uppercase before lowercase

	fmt.Println(slices.IsSorted(nums))

	i, found := slices.BinarySearch(nums, 19)
	fmt.Println(i, found)
}

Đầu ra:

[3 7 19 42 88]
[Bob Carl alice lisa]
true
2 true

Chuỗi được sắp xếp theo byte, nên mọi chữ ASCII viết hoa đều đứng trước mọi chữ viết thường. Với tên người, đó hiếm khi là điều người dùng mong đợi. Phần tiếp theo sẽ sửa điều này.

Package slices có từ Go 1.21. Hàm Sort của nó là pattern-defeating quicksort: O(n log n), tại chỗ, và không ổn định.

Thứ tự tùy chỉnh với SortFunc

slices.SortFunc nhận một hàm so sánh func(a, b T) int. Trả về số âm khi a nên đứng trước, số dương khi b nên đứng trước, và 0 khi hai phần tử bằng nhau. Hàm hỗ trợ cmp.Compare trả về đúng như vậy cho các kiểu có thứ tự.

package main

import (
	"cmp"
	"fmt"
	"slices"
	"strings"
)

func main() {
	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.SortFunc(names, func(a, b string) int {
		return cmp.Compare(strings.ToLower(a), strings.ToLower(b))
	})
	fmt.Println(names)

	// Descending: swap a and b.
	nums := []int{42, 7, 19, 3, 88}
	slices.SortFunc(nums, func(a, b int) int {
		return cmp.Compare(b, a)
	})
	fmt.Println(nums)

	// By length, shortest first.
	words := []string{"banana", "fig", "apple", "kiwi"}
	slices.SortFunc(words, func(a, b string) int {
		return cmp.Compare(len(a), len(b))
	})
	fmt.Println(words)
}

strings.ToLower bên trong phép so sánh cấp phát một chuỗi mới mỗi khi đầu vào có chữ hoa, và phép so sánh chạy khoảng n log n lần. Với slice lớn, hãy tính khóa chữ thường một lần trước. Với tên trong các ngôn ngữ khác (dấu, quy tắc theo vùng), hãy dùng golang.org/x/text/collate, nằm ngoài thư viện chuẩn.

Hàm so sánh phải nhất quán: nếu nó nói a đứng trước b, thì nó phải nói b đứng sau a. Một hàm phá vỡ điều này (ví dụ trả về -1 mỗi khi hai giá trị khác nhau) sẽ cho ra slice sắp xếp sai mà không báo lỗi. Trừ hai số nguyên (return a - b) trông gọn nhưng bị tràn số với giá trị lớn; hãy dùng cmp.Compare.

Sắp xếp struct

Hàm so sánh nhận các phần tử, nên sắp xếp struct theo một trường cũng chỉ là lời gọi y như vậy:

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Compare(a.Salary, b.Salary)
	})
	for _, e := range staff {
		fmt.Println(e.Salary, e.Name)
	}
}

Ở đây các nhân viên có lương bằng nhau có thể ra theo thứ tự bất kỳ, vì SortFunc không ổn định. Nếu cần một thứ tự chắc chắn, hãy phân định bằng thêm trường hoặc dùng sắp xếp ổn định.

Sắp xếp theo nhiều trường

So sánh trường quan trọng nhất trước và chỉ chuyển sang trường tiếp theo khi hòa. cmp.Or (Go 1.22) trả về đối số khác 0 đầu tiên, nên mọi thứ gói gọn trong một dòng:

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	// Department A to Z, then salary high to low, then name A to Z.
	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Or(
			cmp.Compare(a.Dept, b.Dept),
			cmp.Compare(b.Salary, a.Salary),
			cmp.Compare(a.Name, b.Name),
		)
	})
	for _, e := range staff {
		fmt.Printf("%-6s %4d %s\n", e.Dept, e.Salary, e.Name)
	}
}

Đầu ra:

eng     150 Cy
eng     120 Ana
eng     120 Eve
sales    90 Bob
sales    90 Dee

Mọi phép so sánh đều được tính kể cả khi phép đầu tiên đã quyết định, vì chúng chỉ là đối số thông thường. Với so sánh trường thì tốn rất ít. Khi một tiêu chí phụ tốn kém, hãy tự viết chuỗi if c := ...; c != 0 { return c }.

Sắp xếp ổn định

Sắp xếp ổn định giữ các phần tử bằng nhau theo thứ tự ban đầu. Điều này quan trọng khi đầu vào vốn đã có thứ tự ý nghĩa, ví dụ các bản ghi đã sắp theo thời gian mà giờ bạn muốn gom theo người dùng.

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Event struct {
	User string
	Seq  int
}

func main() {
	events := []Event{
		{"bob", 1}, {"ana", 2}, {"bob", 3}, {"ana", 4}, {"bob", 5},
	}
	slices.SortStableFunc(events, func(a, b Event) int {
		return cmp.Compare(a.User, b.User)
	})
	fmt.Println(events)
}

Chương trình in ra [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}]: trong mỗi người dùng, thứ tự ban đầu được giữ nguyên. Sắp xếp ổn định tốn nhiều công hơn, nên chỉ dùng khi thứ tự của các phần tử bằng nhau có ý nghĩa.

Sắp xếp một map

Map không có thứ tự. Để hiển thị map theo thứ tự khóa, hãy sắp xếp các khóa: slices.Sorted(maps.Keys(m)) (Go 1.23). Để sắp xếp theo giá trị, hãy sắp xếp các khóa bằng một phép so sánh tra cứu giá trị:

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

func main() {
	wordCount := map[string]int{"go": 12, "map": 3, "slice": 7, "chan": 7}

	keys := slices.Collect(maps.Keys(wordCount))
	slices.SortFunc(keys, func(a, b string) int {
		return cmp.Or(
			cmp.Compare(wordCount[b], wordCount[a]), // count, high first
			cmp.Compare(a, b),                       // then word, for a stable result
		)
	})
	for _, k := range keys {
		fmt.Println(k, wordCount[k])
	}
}

Tiêu chí phụ theo từ là cần thiết: thiếu nó, chan và slice (cùng là 7) sẽ in ra theo thứ tự khác nhau giữa các lần chạy, vì khóa lấy ra từ map theo thứ tự ngẫu nhiên. Xem thêm ở trang map.

Package sort: sort.Slice và các hàm liên quan

Trước Go 1.21, sắp xếp đi qua package sort. Bạn sẽ gặp nó trong rất nhiều code hiện có:

sort.Ints(nums)
sort.Strings(names)
sort.Slice(staff, func(i, j int) bool {
	return staff[i].Salary < staff[j].Salary
})
sort.SliceStable(staff, func(i, j int) bool { ... })

Những khác biệt nên biết:

Một lỗi hay gặp với sort.Slice là closure tham chiếu tới một slice khác với slice đang được sắp xếp, vì hàm less truy cập theo vị trí. SortFunc không thể mắc lỗi này vì nó đưa thẳng phần tử cho bạn.

Kiểu sort.Interface (Len, Less, Swap) là dạng cũ nhất. Nó vẫn là cách để sắp xếp dữ liệu không nằm trong một slice duy nhất, như hai slice song song phải di chuyển cùng nhau. Từ Go 1.22, sort.Ints, sort.Strings và sort.Float64s chỉ đơn giản gọi slices.Sort.

Lỗi thường gặp

• Tưởng Sort trả về slice đã sắp xếp. Nó sắp xếp tại chỗ và không trả về gì. Dùng slices.Sorted(slices.Values(s)) nếu muốn một slice mới đã sắp xếp, hoặc slices.Clone trước.
• Cho rằng các phần tử bằng nhau giữ nguyên thứ tự. Chỉ các biến thể Stable mới bảo đảm điều đó.
• So sánh bằng phép trừ. a - b bị tràn số. Hãy dùng cmp.Compare.
• Sắp xếp số thực có NaN. cmp.Compare xếp NaN trước mọi giá trị khác, giúp việc sắp xếp nhất quán. Phép so sánh a < b tự viết thì không.