Mengira Isih

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

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

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

Mula-mula tentukan 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 diambil dan kiraan terkumpul 3. Nilai harus 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) output.

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

Akhir sekali, nilai 1 untuk kali kedua dan kiraan kumulatif 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

Atas ialah kandungan terperinci Mengira Isih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!