Go Academy · Lekcja

Sortowanie stabilne

Zachowuj kolejność równych elementów

Sortowanie stabilne to bezpłatna lekcja Go Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Go Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Go Academy zawiera 4 lekcji w sumie.

Czym jest sortowanie stabilne

Stabilne sortowanie zachowuje pierwotną względną kolejność elementów równych. Jeśli dwa rekordy są równoważne według kryterium porównania, ten, który był pierwszy, pozostaje pierwszy.

Dlaczego ma to znaczenie

Stabilność ma znaczenie, gdy sortują Państwo według jednego pola, ale chcą zachować wcześniejszą kolejność elementów o równych wartościach. Na przykład można sortować według miasta, zachowując alfabetyczną kolejność osób w każdym mieście.

sort.Slice nie jest stabilne

Zwykłe sort.Slice nie gwarantuje stabilności. Elementy równe mogą zmienić kolejność. Aby zagwarantować stabilność, użyj sort.SliceStable.

sort.SliceStable

sort.SliceStable ma taki sam podpis jak sort.Slice, ale zachowuje kolejność elementów równych.

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{3, 1, 2, 1}
	sort.SliceStable(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	fmt.Println(nums)
}

Stabilność na przykładzie struktur

Posortuj osoby według wieku. W przypadku sortowania stabilnego osoby w tym samym wieku zachowują kolejność z danych wejściowych.

package main

import (
	"fmt"
	"sort"
)

type Person struct {
	Name string
	Age  int
}

func main() {
	p := []Person{{"Ann", 30}, {"Bob", 25}, {"Cara", 30}}
	sort.SliceStable(p, func(i, j int) bool {
		return p[i].Age < p[j].Age
	})
	fmt.Println(p)
}

Ann przed Cara

W poprzednim przykładzie Ann i Cara mają po 30 lat. Ponieważ Ann występowała wcześniej w danych wejściowych, sortowanie stabilne zachowuje Ann przed Carą w wyniku.

Sortowanie wieloetapowe

Stabilność umożliwia sortowanie etapami. Najpierw sortuj według najmniej ważnego klucza, a następnie według najważniejszego. Każdy stabilny etap zachowuje wcześniejszą kolejność elementów równych.

package main

import (
	"fmt"
	"sort"
)

type Rec struct {
	City string
	Name string
}

func main() {
	r := []Rec{{"Rome", "Zoe"}, {"Oslo", "Ann"}, {"Rome", "Ann"}}
	sort.SliceStable(r, func(i, j int) bool { return r[i].Name < r[j].Name })
	sort.SliceStable(r, func(i, j int) bool { return r[i].City < r[j].City })
	fmt.Println(r)
}

sort.Stable

W przypadku typów implementujących sort.Interface użyj sort.Stable zamiast sort.Sort, aby uzyskać stabilność.

package main

import (
	"fmt"
	"sort"
)

type ByLen []string

func (s ByLen) Len() int           { return len(s) }
func (s ByLen) Less(i, j int) bool { return len(s[i]) < len(s[j]) }
func (s ByLen) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func main() {
	w := []string{"bb", "cc", "a"}
	sort.Stable(ByLen(w))
	fmt.Println(w)
}

Koszt stabilności

Sortowanie stabilne może wymagać nieco więcej pamięci lub czasu niż sortowanie niestabilne. Jeśli nie trzeba zachowywać kolejności elementów równych, zwykłe sort.Slice wystarczy.

Kiedy wybrać sortowanie stabilne

Proszę wybrać sortowanie stabilne, gdy:

Elementy mają istotną kolejność początkową
Sortowanie odbywa się w kilku etapach według różnych kluczy
Równe elementy nie mogą zmienić kolejności

Przykład sprawdzenia stabilności

Dwa elementy o równych kluczach sortowania występują w danych wejściowych w kolejności A, a następnie B. Sortowanie stabilne gwarantuje zachowanie kolejności A przed B w wyniku.

package main

import (
	"fmt"
	"sort"
)

func main() {
	type T struct{ Key, Tag int }
	ts := []T{{1, 100}, {1, 200}, {0, 300}}
	sort.SliceStable(ts, func(i, j int) bool { return ts[i].Key < ts[j].Key })
	fmt.Println(ts)
}

Szybkie sprawdzenie

Sortuje Pan/Pani rekordy według miasta za pomocą sort.SliceStable. Dwa rekordy mają to samo miasto. Co jest gwarantowane?

Podsumowanie

Sortowanie stabilne zachowuje kolejność równych elementów:

sort.SliceStable dla wycinków
sort.Stable dla typów sort.Interface
Umożliwia sortowanie wieloetapowe według różnych kluczy

Często zadawane pytania

Czy lekcja „Sortowanie stabilne” jest bezpłatna?

Tak — pełny tekst „Sortowanie stabilne” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Go Academy, przejdź na CoddyKit PRO. Kurs Go Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Sortowanie stabilne”?

Zachowuj kolejność równych elementów Ćwiczysz Go Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Go Academy?

Nie wymagamy żadnego doświadczenia. Go Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Sortowanie stabilne”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Go Academy?

Tak. Każda lekcja Go Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do Go Academy