Cara melaksanakan pengisihan dalam bahasa Go

Dalam beberapa tahun kebelakangan ini, bahasa Go telah menjadi bahasa pengaturcaraan yang sangat popular, terutamanya dalam pembangunan web dan aplikasi asli awan Semakin ramai pembangun telah memilih bahasa Go. Antaranya, fungsi pengisihan dalam bahasa Go sangat berkuasa dan boleh melaksanakan pelbagai fungsi pengisihan dengan mudah. Dalam artikel ini, kami akan meneroka cara melaksanakan pengisihan dalam bahasa Go.

1. Isih dalam Golang

Bahasa Go menyediakan pakej isihan untuk melaksanakan pelbagai algoritma pengisihan. Mari perkenalkan dua fungsi utama dalam pakej isihan.

1. isih.Slice

Fungsi sort.Slice boleh digunakan untuk mengisih jenis data Slice Prototaip fungsinya adalah seperti berikut:

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

Antaranya, parameter slice mewakili kepingan yang perlu diisih, parameter less ialah fungsi pertimbangan dan nilai pulangan mestilah daripada jenis bool. Fungsi penghakiman less digunakan untuk menentukan hubungan saiz setiap elemen dalam kepingan Jika benar dikembalikan, ini bermakna elemen hadapan lebih kecil daripada elemen belakang dan kedudukan perlu ditukar.

Ambil isihan keping jenis int sebagai contoh Kod sampel adalah seperti berikut:

package main

import (
    "fmt"
    "sort"
)

func main() {
    ints := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 4}
    sort.Slice(ints, func(i, j int) bool {
        return ints[i] < ints[j]
    })
    fmt.Println(ints)
}

Atur cara di atas boleh mengisih keping jenis int, dan hasilnya akan diisih daripada. kecil ke besar.

2. isih.Isih

Fungsi isihan.Isih boleh digunakan untuk mengisih jenis yang melaksanakan isihan.Antara muka antara muka prototaipnya adalah seperti berikut:

func Sort(data Interface)

Antaranya, parameter data mewakili data yang perlu diisih dan parameter mestilah jenis yang melaksanakan jenis. Antara muka antara muka. Takrif isihan. Antara muka antara muka adalah seperti berikut:

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

isih.Antara muka mentakrifkan tiga fungsi yang diperlukan untuk mengisih: Len() mengembalikan panjang data dan Less(i, j int) digunakan untuk tentukan kedudukan i Sama ada data lebih kecil daripada data pada kedudukan j, Swap(i, j int) menukar data pada kedudukan i dengan data pada kedudukan j.

Ambil menyusun tatasusunan rentetan sebagai contoh Kod sampel adalah seperti berikut:

package main

import (
    "fmt"
    "sort"
)

type stringSlice []string

func (s stringSlice) Len() int {
    return len(s)
}

func (s stringSlice) Less(i, j int) bool {
    return s[i] < s[j]
}

func (s stringSlice) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func main() {
    words := stringSlice{"foo", "bar", "baz", "qux"}
    sort.Sort(words)
    fmt.Println(words)
}

Atur cara di atas boleh mengisih tatasusunan rentetan, dan hasilnya akan diisih dari kecil ke besar. .

2. Pelaksanaan algoritma pengisihan biasa

Dalam pakej isihan, algoritma pengisihan biasa dilaksanakan, seperti isihan cepat, isihan Bukit, dsb. Algoritma ini berdasarkan isihan. Antara muka antara muka . Selain menggunakan fungsi yang disediakan oleh pakej isihan, pembangun juga boleh melaksanakan sendiri algoritma pengisihan.

1. Isih cepat

Isih cepat menggunakan strategi bahagi-dan-takluk untuk membahagikan urutan kepada dua sub-urutan Proses khusus adalah seperti berikut:

• Dari urutan Pilih elemen sebagai nombor asas.
• Letakkan semua elemen yang lebih kecil daripada nombor asas di hadapan nombor asas, dan letakkan elemen yang lebih besar daripada nombor asas selepas nombor asas.
• Ulang langkah di atas untuk dua urutan sebelum dan selepas nombor rujukan.

Berikut ialah kod sampel untuk isihan pantas:

package main

import "fmt"

func quickSort(arr []int, left, right int) {
    if left < right {
        partIndex := partition(arr, left, right)
        quickSort(arr, left, partIndex-1)
        quickSort(arr, partIndex+1, right)
    }
}

func partition(arr []int, left, right int) int {
    pivot := left
    for i:= left + 1; i <= right; i++ {
        if arr[i] < arr[left] {
            pivot++
            arr[pivot], arr[i] = arr[i], arr[pivot]
        }
    }
    arr[left], arr[pivot] = arr[pivot], arr[left]
    return pivot
}

func main() {
    arr := []int{5, 0, 3, 2, 1, 6, 8, 9, 7, 4}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

2. Isih bukit

Isih bukit, juga dikenali sebagai kenaikan menurun Algoritma pengisihan ialah pelaksanaan isihan sisipan yang lebih cekap Ia membahagikan elemen untuk diisih kepada beberapa kumpulan dan masing-masing melakukan pengisihan sisipan.

Berikut ialah contoh kod untuk pengisihan Bukit:

package main

import "fmt"

func shellSort(arr []int) []int {
    n := len(arr)
    for gap := n / 2; gap > 0; gap /= 2 {
        for i := gap; i < n; i++ {
            for j := i - gap; j >= 0 && arr[j] > arr[j+gap]; j -= gap {
                arr[j], arr[j+gap] = arr[j+gap], arr[j]
            }
        }
    }
    return arr
}

func main() {
    arr := []int{5, 0, 3, 2, 1, 6, 8, 9, 7, 4}
    fmt.Println(shellSort(arr))
}

3 Ringkasan

Artikel ini memperkenalkan kaedah melaksanakan pengisihan dan algoritma pengisihan yang biasa digunakan dalam Go. bahasa. Antaranya, isihan cepat dan isihan Bukit adalah salah satu algoritma pengisihan yang paling biasa digunakan, dan kedua-duanya adalah kaedah pelaksanaan yang agak cekap. Apabila menggunakan pakej isihan, pembangun perlu mengatasi tiga kaedah pengisihan. Antara muka untuk beberapa struktur data yang lebih kompleks, mereka juga boleh melaksanakan algoritma pengisihan mereka sendiri untuk menyelesaikan operasi pengisihan.

Atas ialah kandungan terperinci Cara melaksanakan pengisihan dalam bahasa Go. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!