Mengira Isih

Berikut ialah algoritma isihan untuk digunakan bagi tatasusunan integer atau struktur yang dikunci oleh integer. Terutamanya berguna apabila julat integer adalah mengikut tertib saiz input.

Idea utama adalah untuk menentukan kekerapan kejadian integer dan menggunakannya untuk menentukan susunan yang diisih.

Contoh: katakan kita mendapat tatasusunan {1,3,1,2}.

Tentukan dahulu julat integer, maks dan min, 1 dan 3 untuk input ini.

Seterusnya buat tatasusunan, panggil tatasusunan kiraan, iaitu saiz julat integer+1, jadi 3 (3-1+1) dalam kes ini.
Lelaran ke atas tatasusunan input, menambah masukan yang sesuai dalam kiraan. Kiraan nilai input yang diberikan akan diletakkan pada kiraan[nilai - min]. Untuk input yang diberikan, kiraan[0] akan menahan kiraan untuk nilai 1.

Ini menghasilkan tatasusunan kiraan: {2,1,1}

Sekarang tentukan kiraan kumulatif, yang pada asasnya adalah kiraan[i] = kiraan[i-1]+kiraan[i].

Ini menghasilkan tatasusunan kiraan terkumpul: {2,3,4}

Buat tatasusunan output untuk input yang diisih.

Sekarang, ulangi input dalam susunan terbalik.

Pada setiap langkah, dapatkan semula kiraan terkumpul untuk nilai dalam tatasusunan input. Nilai akan diletakkan pada indeks tatasusunan output yang sepadan dengan kiraan yang diambil - 1. Kemudian kurangkan nilai kiraan terkumpul.

Dalam langkah pertama, nilai 2 diperoleh semula dan kiraan terkumpul 3. Nilai itu hendaklah diletakkan pada indeks 2 (3-1) dalam output.

Dalam lelaran seterusnya, nilai 1 dan kiraan kumulatif 2; jadi '1' ini diletakkan pada indeks 1 (2-1) keluaran.

Bersambung, nilai 3 dan kiraan kumulatif 4; meletakkannya pada indeks 3 output.

Akhir sekali, nilai 1 untuk kali kedua dan kiraan terkumpul 1 (memandangkan kiraan itu dikurangkan pada kali pertama ia dilihat); jadi '1' ini diletakkan pada indeks 0 output.

, Lihat bagaimana lelaran secara terbalik mengekalkan susunan elemen yang sama menjadikan jenis 'stabil'

Tatasusunan diisih yang terhasil ialah {1,1,2,3}

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min+1)
    for _, v := range in {
        counts[v-min]++
    }
    // determine cumulative counts
    for i := 1; i < len(counts); i++ {
        counts[i] = counts[i-1] + counts[i]
    }
    // create the output array
    out := make([]int, len(in))
    for i := range in {
        v := in[len(in)-1-i]
        out[counts[v-min]-1] = v
        counts[v-min]--
    }
    return out
}

Bolehkah ia dibuat lebih cekap? Tinggalkan komen dan cadangan anda di bawah.

Terima kasih!

Kod untuk siaran ini dan semua siaran dalam siri ini boleh didapati di sini

以上是Mengira Isih的详细内容。更多信息请关注PHP中文网其他相关文章！