Özet - Counting sort

Counting sort uygulayıp sonucu yazdıran mini görev yaparsın.

Özet - Counting sort

Counting sort: say + birikimli + geriye yerleştir. Karşılaştırmasız, O(n + k), kararlı. k anahtar aralığıdır.

Küçük tamsayı aralığında hızlıdır; büyük aralıkta bellek patlar. Negatif değerler için kaydırma gerekir.

Radix sort'un alt sıralayıcısı olarak kullanılır; bu sayede büyük sayılar da sıralanabilir.

Uygulama Özet: counting sort

counting_sort(arr) yaz. print(counting_sort([5,1,4,2,8,2])) ile [1, 2, 2, 4, 5, 8] yazdır.

Örnek çözümü göster

def counting_sort(arr):
    # Sayarak sırala
    if not arr:
        return []
    k = max(arr) + 1
    count = [0] * k
    for x in arr:
        count[x] += 1
    for i in range(1, k):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    return output
print(counting_sort([5, 1, 4, 2, 8, 2]))

Kendini test et

Özet - Counting sort: kavramları eşleştir

Maliyet

O(n+k)
Bellek

O(k)
Kararlı

Evet
Aralık

Dar olmalı

Birikimli

count[i] ____count[i-1]

Cevabı göster

count[i] +=count[i-1]

Counting sort karşılaştırma yapar mı?
- Hayır
- Sadece küçük dizide
- Sadece büyük dizide
- Evet, her zaman
Cevabı göster

Hayır — Hayır

Sıradaki ders: Radix mantığı

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler