Kararlı alt sıralama

Her başamakta kararlı bir alt sıralama kullanmanın önemini öğrenirsin.

Kararlı alt sıralama

Tam radix sort, basamak dolaşma adımını her basamak için tekrarlar. En az anlamlı başamaktan başlar, en çok anlamlıya kadar gider.

Her geçiş kararlı olduğu için, bir önceki geçişin sırası korunur ve yeni basamak bilgi ekler. Sonunda dizi tam sıralanır.

Basamak sayısı d = len(str(max(arr))). Toplam maliyet O(dn).

Negatif sayılar

Radix sort varsayılan olarak negatif olmayan tamsayıları sıralar. Negatif sayılar için iki yaygın yöntem vardır.

Birincisi: tüm sayılara sabit bir kaydırma ekleyip pozitif yap, sırala, sonra kaydırmayı çıkar. İkincisi: işaret ve mutlak değere göre ayrı grupla.

Her iki yöntem de O(dn) maliyeti korur, ama uygulama daha dikkatli ister.

Uygulama Radix sort

radix_sort(arr) yaz. LSD yöntemiyle basamak basamak sırala. print(radix_sort([170, 45, 75, 90, 2, 24])) ile [2, 24, 45, 75, 90, 170] 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([170, 45, 75, 90, 2, 24]))

Kendini test et

Kararlı alt sıralama: kavramları eşleştir

LSD

Başlangıç
Geçiş

Kararlı
Basamak sayısı

d
Toplam

O(dn)
Radix sort kaç geçiş yapar?
- 1
- log n
- n
- d (basamak sayısı)
Cevabı göster

d (basamak sayısı) — d (basamak sayısı)

Döngü sınırı

for d in range(____):

Cevabı göster

for d in range(max_digits):

Sıradaki ders: Özet - Radix sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler