Özet - Radix sort

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

Özet - Radix sort

Radix sort: basamak basamak, LSD'den başlayarak, kararlı counting sort ile. Karşılaştırmasız, O(dn).

d basamak sayısıdır; tamsayılar için log k kadardır (k en büyük değer). Büyük sayılar için bile etkilidir.

Negatif sayılar için kaydırma gerekir. Kararlılık şarttır; aksi halde sonuç yanlış olur.

Uygulama Özet: radix sort

radix_sort(arr) yaz. print(radix_sort([3,1,4,1,5,9,2,6])) ile [1, 1, 2, 3, 4, 5, 6, 9] yazdır.

Örnek çözümü göster

def get_digit(n, d):
    return n // (10 ** d) % 10
def counting_by_digit(arr, d):
    count = [0] * 10
    for x in arr:
        count[get_digit(x, d)] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        digit = get_digit(arr[i], d)
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
    return output
def radix_sort(arr):
    # Basamak basamak sırala
    if not arr:
        return arr
    max_digits = len(str(max(arr)))
    for d in range(max_digits):
        arr = counting_by_digit(arr, d)
    return arr
print(radix_sort([3, 1, 4, 1, 5, 9, 2, 6]))

Kendini test et

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

Yöntem

LSD
Alt sıralayıcı

Counting sort
Maliyet

O(dn)
Kararlı

Şart

Başlangıç

En az anlamlı basamak: d = ____

Cevabı göster

En az anlamlı basamak: d = 0

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

Hayır — Hayır

Sıradaki ders: Proje: Genel bakış

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler