Apakah kaedah pelaksanaan pakej isihan dalam bahasa Go?

Go ialah bahasa yang ditaip kuat, kodnya ringkas dan mudah dibaca serta mempunyai prestasi yang cekap, jadi ia semakin popular di kalangan pembangun. Antaranya, pakej isihan ialah bahagian penting pustaka standard bahasa Go Ia menyediakan fungsi pengisihan untuk hirisan dan jenis koleksi yang ditentukan pengguna. Artikel ini akan memperkenalkan pelaksanaan pakej isihan dalam bahasa Go.

Takrif isihan.Antara muka antara muka dalam pakej isihan adalah seperti berikut:

type Interface interface {
    // 嵌入内置的len函数，返回集合元素个数
    Len() int
    // 比较索引i和索引j上的元素
    Less(i, j int) bool
    // 交换索引i和索引j上的元素
    Swap(i, j int)
}

Melalui antara muka ini, kita boleh melaksanakan jenis algoritma isihan tersuai.

Dalam pakej isihan, terdapat tiga kaedah pengisihan utama yang dilaksanakan: Isih, Stabil dan Hiris, yang akan diperkenalkan satu persatu di bawah.

1. Isih

Kaedah Isih mengisih kepingan masuk dan menggunakan algoritma isihan pantas yang dioptimumkan. Ia boleh dilihat daripada kod sumber: jenis hirisan ialah []Jenis, jadi anda boleh menggunakan hirisan Jenis untuk memanggil terus kaedah Isih (Jenis ialah jenis elemen dalaman bagi hirisan).

func Sort(data Interface) {
    n := data.Len()
    quickSortFunc(n, swapFunc(data), maxDepth(n))
}

Kaedah Isih memanggil fungsi quickSortFunc secara dalaman untuk melaksanakan operasi pengisihan Fungsi ini akan memanggil dirinya secara rekursif sehingga rekursi selesai atau sub-kepingan yang dibahagikan terlalu kecil.

// 快速排序
// n 为切片大小
// swap 为交换函数，可以通过sort.Interface中的swap方法来实现
func quickSortFunc(n int, swap swapFunc, maxDepth int) {
    // 插入排序，Num^1为偶数，&1可用来判断奇偶性
    if n < insertionSortThreshold {
        for i := 1; i < n; i++ {
            for j := i; j > 0 && swap(j-1, j); j-- {
            }
        }
        return
    }
    if maxDepth == 0 {
        heapSortFunc(n, swap)
        return
    }
    maxDepth--
    third := n / 2
    // 选择枢纽元
    if n > med3Threshold {
        m0 := 0
        m1 := n / 2
        m2 := n - 1
        if n > 40 {
            s := n / 8
            m0 = med3(swap, 0, s, 2*s)
            m1 = med3(swap, m1-s, m1, m1+s)
            m2 = med3(swap, n-1-2*s, n-1-s, n-1)
        }
        third = med3(swap, m0, m1, m2)
    }
    // 挖洞填数
    // z正反代表着大或小于枢纽元素
    z := n - 1
    // p代表在枢纽元素左边的指针，q代表在枢纽元素右边的指针
    p := 0
    q := z
    for {
        for ; p < n && !swap(p, third); p++ {
        }
        for ; q >= 0 && swap(q, third); q-- {
        }
        if p >= q {
            break
        }
        swap(p, q)
        if p == third {
            third = q
        } else if q == third {
            third = p
        }
        p++
        q--
    }
    // 对子切片递归调用quickSortFunc函数
    quickSortFunc(p, swap, maxDepth)
    quickSortFunc(n-p-1, swapFuncAt(swap, p+1), maxDepth)
}

2. Stabil

Kaedah Stabil ialah algoritma pengisihan stabil yang boleh mengekalkan kedudukan relatif unsur yang sama tidak berubah. Operasi ini terutamanya untuk mengisih beberapa keping yang tidak mematuhi peraturan pengisihan kaedah Isih dengan cara yang agak teratur, seperti pengisihan separuh unsur dalam rajah.

func Stable(data Interface) {
    // length 为切片长度
    length := data.Len()
    // mergeSort函数就是归并排序
    mergeSort(data, 0, length)
}

Algoritma ini sangat cekap ia bukan sahaja algoritma pengisihan yang stabil, tetapi juga mempunyai kerumitan O(n log n).

3. Slice

Slice sorts sub-slices, iaitu, sorts slice [mula, end).

func Slice(slice interface{}, less func(i, j int) bool) {
    // 利用反射获取slice值信息
    rv := reflect.ValueOf(slice)
    // 获取长度信息
    vlen := rv.Len()
    // 初始化并调用SortInterface，参数为lessSlice
    reflect.Sort(newSortInterface(rv, makeLessSlice(less, vlen)))
}

Perlu diambil perhatian bahawa pelaksanaan kaedah kurang fungsi mesti dilaksanakan mengikut kaedah Isih Kurang. Antara muka fungsi yang kurang akan lulus dalam dua indeks i dan j dan mengembalikan nilai bool : tentukan unsur i Adakah ia kurang daripada unsur bernombor j Jika ya, tukar(i, j).

Di atas ialah pelaksanaan ringkas pakej isihan dalam bahasa Go Daripada pengenalan di atas, kita dapati bahawa pakej isihan adalah agak mudah untuk dilaksanakan, tetapi mempunyai prestasi pengisihan yang cekap, dan juga menyediakan pembangun dengan. kemudahan yang hebat.

Atas ialah kandungan terperinci Apakah kaedah pelaksanaan pakej isihan dalam bahasa Go?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!