איך עושים מיון דלי?

2024 מְחַבֵּר: Lynn Donovan | [email protected]. שונה לאחרונה: 2024-01-18 08:24

מיון הדלי פועל באופן הבא:

1. הגדר מערך של ריקים בהתחלה " דליים ".
2. פיזור: עברו על המערך המקורי, והכניסו כל אובייקט לתוכו דְלִי .
3. סוג כל אחד לא ריק דְלִי .
4. איסוף: בקר ב דליים לפי הסדר ולהחזיר את כל האלמנטים למערך המקורי.

יתר על כן, מהו מיון דלי עם דוגמה?

כמו כן, תמצא עבודה דוגמאות שֶׁל מיון דלי ב-C, C++, Java ו-Python. מיון דלי הוא מִיוּן טכניקה כי מיון האלמנטים על ידי חלוקה תחילה של האלמנטים למספר קבוצות שנקראות דליים . האלמנטים מפוזרים תחילה לתוך דליים ואז האלמנטים של דליים הם מְמוּיָן.

יתר על כן, היכן משמש מיון דלי? מיון דלי שימושי בעיקר כאשר הקלט מתחלק באופן אחיד על פני טווח. לדוגמה, שקול את הבעיה הבאה. סוג קבוצה גדולה של מספרי נקודה צפה שנמצאת בטווח שבין 0.0 ל-1.0 ומחולקת באופן אחיד על פני הטווח.

בהתחשב בכך, איך מוצאים את מספר הדליים במיון דלי?

אם דליים יש אורך 2^k, כל אחד דְלִי יש מידה אחת, ו מיון דלי מתדרדר לספירה סוג . אז אתה רוצה כל אחד דְלִי גודל להיות יותר מ-1. אם יש לנו n דליים , ו-msbits(x, k) מחזיר 2^k ערכים, ולאחר מכן כל אחד דְלִי הגודל הוא 2^k/n.

מהי מורכבות הזמן של מיון דלי?

הממוצע מורכבות הזמן ל מיון דלי הוא O(n + k). הכי גרוע מורכבות הזמן הוא O(n²). החלל מוּרכָּבוּת ל מיון דלי הוא O(n+k).