Isihan Tanpa Perbandingan dan sort() Python
Terokai isihan pengiraan dan isihan radix untuk tatasusunan integer, serta fahami cara Timsort Python berfungsi di sebalik tabir bagi panggilan sort terbina dalam.
Isihan Tanpa Perbandingan dan sort() Python ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Had Bawah O(n log n) untuk Perbandingan
Mana-mana algoritma pengisihan yang menentukan susunan hanya melalui perbandingan elemen memerlukan sekurang-kurangnya Ω(n log n) perbandingan dalam kes terburuk. Hal ini dibuktikan melalui hujah pepohon keputusan: mengisih n elemen memerlukan pembezaan antara n! susunan yang mungkin. Pepohon keputusan binari (setiap nod ialah perbandingan) memerlukan sekurang-kurangnya log₂(n!) ≈ n log₂(n) aras. Untuk memecahkan had ini, kita memerlukan maklumat tambahan tentang elemen — contohnya, elemen itu ialah nombor bulat dalam julat terhad.
import math
for n in [5, 10, 100, 1000]:
lower_bound = n * math.log2(n)
factorial_log = sum(math.log2(i) for i in range(1, n+1))
print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')
# n log n is a tight bound on comparison-based sortingIsihan Pengiraan: Isih mengikut Kekerapan
Isihan pengiraan berfungsi dengan mengira kekerapan setiap nilai, kemudian membina semula tatasusunan terisih daripada kiraan tersebut. Ia memerlukan pengetahuan awal tentang julat nilai [0, k). Kerumitan masa: O(n + k); kerumitan ruang: O(k). Untuk k yang kecil berbanding n (contohnya, mengisih umur 0–120 atau angka tunggal), isihan pengiraan mengatasi semua algoritma pengisihan berasaskan perbandingan. Bagi k yang besar, kos ruang O(k) menjadikannya tidak praktikal.
def counting_sort(arr, k=None):
if not arr: return []
if k is None: k = max(arr) + 1
count = [0] * k
for n in arr:
count[n] += 1
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)Pengisihan Pengiraan Stabil dengan Kiraan Kumulatif
Untuk pengisihan pengiraan yang stabil (penting apabila mengisih objek mengikut kunci), kira kiraan kumulatif supaya cum[v] memberikan kedudukan permulaan nilai v dalam hasil. Imbas tatasusunan masukan dari kanan ke kiri, letakkan setiap unsur pada kedudukan cum[key] - 1 dan kurangkan kedudukan itu. Ini menghasilkan pengisihan stabil — unsur yang mempunyai kunci sama muncul dalam susunan relatif asalnya.
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]Pengisihan Radix: Isih Digit demi Digit
Pengisihan radix mengisih nombor bulat digit demi digit, daripada digit paling kurang signifikan (LSD) hingga digit paling signifikan (MSD), menggunakan pengisihan stabil (seperti pengisihan pengiraan) pada setiap kedudukan digit. Selepas d laluan (satu bagi setiap digit), tatasusunan diisih sepenuhnya. Kerumitan masa: O(d × (n + k)), dengan d = bilangan digit dan k = asas (biasanya 10). Bagi n nombor bulat yang dihadkan oleh W, d = log_k(W), maka jumlahnya ialah O(n log_k(W)).
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]Pengisihan Baldi: Agihkan kepada Baldi
Pengisihan baldi mengagihkan unsur ke dalam bilangan baldi yang tetap berdasarkan julat nilai, mengisih setiap baldi (menggunakan pengisihan sisipan untuk baldi kecil), kemudian mencantumkannya. Bagi data yang teragih secara seragam dalam [0, 1), n baldi memberikan masa purata O(n). Masa: O(n + k) secara purata, dan O(n²) dalam kes terburuk (semua unsur berada dalam satu baldi). Kaedah ini paling berguna apabila taburan data diketahui dan hampir seragam.
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listTimsort Python di Sebalik Tabir
sorted() dan list.sort() Python menggunakan Timsort, yang direka oleh Tim Peters pada tahun 2002. Timsort ialah gabungan pengisihan gabungan dan pengisihan sisipan. Ia mengimbas 'jujukan semula jadi' (subjujukan yang sudah diisih) dan menggunakan pengisihan sisipan untuk membina jujukan sehingga 64 unsur. Kemudian, ia menggabungkan jujukan menggunakan pengisihan gabungan dengan beberapa pengoptimuman: lompatan (melangkau unsur secara pukal apabila satu jujukan lebih dominan) dan penindanan panjang jujukan.
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')sort() Python berbanding sorted(): Perbezaan Utama
list.sort() mengisih di tempat asal, mengembalikan None dan hanya berfungsi pada senarai. sorted(iterable) berfungsi pada sebarang objek boleh lelar (tupel, penjana, kamus) dan mengembalikan senarai baharu. Kedua-duanya menerima parameter key dan reverse. Pepijat biasa: menetapkan nilai pulangan lst.sort() kepada pemboleh ubah lalu tertanya-tanya mengapa nilainya None. Gunakan sentiasa sorted() apabila memerlukan versi yang telah diisih dan mahu mengekalkan versi asal.
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)Kunci Pengisihan Tersuai dalam Temu Duga
Pengisihan Python menerima fungsi key yang dinilai sekali bagi setiap unsur (tidak seperti pembanding C yang dipanggil bagi setiap pasangan). Kunci pengisihan biasa dalam temu duga: len untuk panjang rentetan, lambda x: -x untuk susunan menurun, lambda x: (x[1], x[0]) untuk pengisihan berbilang kunci, dan str.lower untuk pengisihan tanpa mengambil kira huruf besar atau kecil. Pengisihan Python dijamin stabil, jadi pengisihan berbilang kunci berfungsi dengan betul.
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]Bila Perlu Menggunakan Setiap Pengisihan dalam Temu Duga
Pilih pengisihan yang betul mengikut konteks:
- Gunakan sorted()/list.sort() Python: pilihan lalai untuk semua soalan temu duga — Timsort adalah optimum
- Pengisihan pengiraan: apabila nilai ialah nombor bulat kecil dengan julat terhad (0 hingga k, k kecil)
- Pengisihan radix: apabila mengisih banyak nombor bulat dengan lebar bit atau bilangan digit yang diketahui
- Pengisihan baldi: apabila data terdiri daripada nombor perpuluhan yang teragih seragam dalam julat yang diketahui
- Laksanakan pengisihan gabungan: apabila diminta menulis pengisihan stabil O(n log n) dari awal
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]Pengisihan Tanpa Pengisihan: K Unsur Teratas dengan Timbunan
Banyak soalan temu duga meminta hasil yang 'menyerupai pengisihan' tanpa memerlukan pengisihan penuh. Untuk mencari k unsur teratas: timbunan minimum bersaiz k berjalan dalam O(n log k) — lebih pantas daripada O(n log n) apabila k << n. Untuk mencari unsur terbesar ke-k: quickselect mengambil masa purata O(n). Untuk mencari median: pendekatan dua timbunan mengambil masa O(log n) bagi setiap sisipan. Pendekatan pengisihan separa ini wajar diketahui sebagai alternatif yang lebih pantas daripada pengisihan penuh.
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
if lo >= hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]; i = lo - 1
for j in range(lo, hi):
if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5Kestabilan Pengisihan dalam Pengisihan Berbilang Kunci
Kestabilan membolehkan pengisihan berbilang kunci dilakukan dengan betul: isih mengikut kunci sekunder dahulu (secara stabil), kemudian mengikut kunci primer (secara stabil). Susunan sekunder dikekalkan bagi nilai yang sama pada kunci primer. Teknik ini digunakan dalam pangkalan data (ORDER BY col1, col2) dan dalam pengisihan radix (setiap laluan digit mesti stabil supaya keseluruhan algoritma betul). Pengisihan Python sentiasa stabil, jadi corak ini berfungsi dengan boleh dipercayai.
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini anda telah belajar bahawa: pengisihan berasaskan perbandingan mempunyai had bawah O(n log n) — untuk memecahkan had ini diperlukan maklumat bukan berasaskan perbandingan seperti nombor bulat yang terhad, pengisihan pengiraan mencapai O(n + k) dengan mengira kekerapan, pengisihan radix memproses digit dengan jumlah O(d × (n + k)), dan pengisihan baldi memanfaatkan taburan seragam untuk mencapai O(n) secara purata, serta Timsort Python ialah pilihan lalai yang praktikal — stabil, mempunyai kes terburuk O(n log n), kes terbaik O(n), dan lebih pantas daripada sebarang alternatif yang ditulis sendiri untuk data sebenar. Seterusnya, kita akan menguasai carian binari klasik.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Isihan Tanpa Perbandingan dan sort() Python” percuma?
Ya — teks penuh “Isihan Tanpa Perbandingan dan sort() Python” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Isihan Tanpa Perbandingan dan sort() Python”?
Terokai isihan pengiraan dan isihan radix untuk tatasusunan integer, serta fahami cara Timsort Python berfungsi di sebalik tabir bagi panggilan sort terbina dalam. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Isihan Tanpa Perbandingan dan sort() Python” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Isihan Buih dan Isihan Sisipan
- Isihan Gabung: Bahagi, Isih, Gabung
- Isihan Pantas dan Pemilihan Pangsi
- Isihan Tanpa Perbandingan dan sort() Python