מיזוג-מיון ב-Java

כל מתכנת חייב לחשוב בהתחלה על התוכנית/תוכנית/ארכיטקטורה של עבודה עתידית, אחרת הכל מסתיים בבלגן, עם אנרכיה מוחלטת. כמו בכל פוסט, בהתחלה אתה צריך תוכנית, בואו נתחיל.

• 1) בואו ניקח את הנושא של מיזוג מיונים למתחילים.
• 2) ניצור ארכיטקטורה ותכנית לעבודה נוספת.
• 3) נעבור ונתאר את כל חלקי התכנית.
• 4) בואו נבדוק את הביצועים והאיכות.

• 2.1) מהו מיון מיזוג.
• 2.2) תיאור חתימות אפשריות.
• 2.3) תן דוגמה.
• 2.4) תאר את היישום ב-Java באמצעות דוגמה.
• 2.5) כל דבר נוסף.

מיזוג - מיון מיזוג ב-Java

מרמז על העיקרון של "הפרד ומשול". מה הרעיון ומה המשמעות שלו?

1. מִיוּן.

   נחלק את המערך לחלקים עד שהוא שווה לאלמנט אחד. כל רכיב אחד ממוין.

2. מיזוג.

   מיזוג אלמנטים ממוינים.
   מבוסס על העיקרון של שתי חפיסות קלפים. אנו מניחים 2 חפיסות קלפים על השולחן עם ערכם למעלה, והקלף הנמוך ביותר מונח בערימת הקלפים השלישית שנוצרה. בסופו של דבר, אם נגמרו לנו הקלפים בחפיסה מסוימת, נעביר אותם אחד אחד לחפיסה המתקבלת. התוצאה תהיה מיזוג של שני מערכים ממוינים, מערך אחד חדש וממוין.

הזמן המושקע הוא O(n log2 n). המיון נחשב למהיר למדי. בקצרה על מורכבות אלגוריתמית, אם מישהו צריך אותה. לעתים קרובות אתה יכול לראות פונקציות כמו:

Sort(A, p, q);
Merge(A, p, q, r);

זה בערך אותו דבר, רק מקושר לאינדקס. המשתנים בהם הם:

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

אם המשתנים הללו לא מתוארים, אז מי שמבקש לעשות פונקציה כזו בעצמו לא יודע מה הוא רוצה. ואתה תצטרך לסרוק את גוגל כדי לגלות מה זה, כנראה שתמצא את זה, אולי. בואו ניתן דוגמה למיון שלנו. יש מערך {6, 1, 3, 5, 2, 4, 7, 8}, אם אורכו גדול מ-1, אז נחלק אותו ל-2 חלקים ונקבל את החלק השמאלי {6, 1, 3, 5}ואת החלק הימני {2, 4, 7, 8}. אנו ממשיכים בפעולת החלוקה ל-2 חלקים עד שאורכו גדול מ-1. כתוצאה מכך, נקבל חבורה של מערכים באורך של אלמנט אחד, כלומר: {6} {1} {3} {5} {2} {4} {7} {8}. היישום בג'אווה הוא משהו כזה:

public int [] sortArray(int[] arrayA){ // sorting Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

בשלב הבא אתה צריך למזג את המערכים האלה ל-1. איך זה נעשה? כדי להימנע מלעבור על כל מערך מספר פעמים, הבה נזין מדדי מיקום עבור כל מערך. לאחר מכן נעבור פעם אחת לולאה, שווה לאורך הסכום של שני המערכים הללו. קח את המערך הראשון ואת המערך השני, ולקחת את האלמנט הראשון, השוו בין אלמנט מספר 1 במערך הראשון לבין אלמנט מספר 1 במערך השני ? הקטן יותר ממוקם במערך המתקבל. חשוב כאן שאם לקחנו אלמנט מהמערך הראשון, אז כשהלולאה עוברת, הוא צריך להתייחס לאלמנט ה-2 של המערך הראשון ולאלמנט ה-1 של המערך השני. לשם כך, עליך להגדיל את האינדקס של המערך השני ב-+1, וכאשר בודקים, להחסיר אותו ממספר המחזור, באופן דומה עבור המערך הראשון. האם ברור למה לעשות את זה? או ששום דבר לא ברור בכלל? :-) לדוגמה, ישנם 2 מערכים: {1}{4}{8}ויש {3}{6}{7} מחזור:

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

במעבר הראשון של הלולאה, מתברר ש arrayC[1] = {1}: לקחנו את האלמנט הזה מהמערך הראשון. לאחר מכן, כאשר עוברים על הלולאה השנייה, עלינו כבר להשוות את האלמנט {4}ו {3}, אך בכדי לעשות זאת עלינו לקחת בחשבון את מדדי המיקום ואת ההיסט של שני המערכים, לשם כך אנו נכנסים אליהם.

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

אבל זה לא הכל, אתה צריך לקחת בחשבון שמערך כלשהו עשוי להסתיים מוקדם יותר. לדוגמה, יש 3 מערכים: {1}{3}{5}והמערך {6}{7}{9} הראשון יסתיים לפני שהשני יגיע, בשביל זה צריך להזין צ'ק ובאופן עקרוני פונקציית המיזוג מוכנה.

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

הדבר הקשה ביותר במיון הזה הוא עקרון המעבר הרקורסי. הָהֵן. אנחנו זורקים את הצד השמאלי לרקורסיה עד שהוא מתחלק ב-2, ואז משחררים אותו בחזרה, במילים זה מאוד מסובך ומבלבל, אבל כשאתה מנסה לדמיין, אם זה עדיין לא ברור, אז זה בלאגן מוחלט. ניקח את המערך: {2}{1}{4}{3}. רקורסיית המיון הראשונה תחלק אותו ל-2 חלקים ותפעיל את הפונקציה שוב עם אלמנטים 2-1 , ואז שוב עם אלמנטים 2 ו -1 , תחזיר אותם בתורם, כך שהם יכנסו קודם לפונקציית המיזוג, ו- 1-2 יבוא החוצה , אז הרקורסיה תחזור אחורה ותזרוק 4-3 למיזוג , ואז 4 ו -3 , לאחר מכן המיזוג יחזור 3-4 , ורק אז הרקורסיה תסתובב שוב ו- 1-2 ו- 3-4 ייכלל במיזוג , והמערך הממוין יוחזר 1-2-3-4 . ובכן, זה הכל, המיון מורכב משתי פונקציות.

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

אם תכתוב איזשהו עיקרי, תקבל משהו כמו:

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

מבחינתי המיון הזה היה כישלון מוחלט, היו מיליון שאלות, אבל אין תשובות, חפרתי בכל האינטרנט, קראתי שוב, צפיתי בהמון סרטונים, אבל כמו תמיד, מצאתי את התשובות רק בעצמי. ורק כשהתחלתי לכתוב פתרון שונה לגמרי מזה שמבריק בכל מקום) אבל בסוף יצא דומה לכל האחרים))) המיון הוא בעצם הכי פשוט, העיקר להציג אותו בצורה אינטראקטיבית בפעולה, ו הכל יסתדר אם אתה מבין, אני אכין סרטון)))) עד עכשיו, זה כל מה שהספיק לי: מיזוג מיון מיזוג-מיין הדבר הכי חשוב הוא תמיד להכין תוכנית מ- ההתחלה. עדיף לחכות קצת ולחשוב לפני שמתחילים לעשות משהו. זה אולי ייקח יותר זמן, אבל יופיעו הבנה ופתרון במקום שתצטרך לשכתב אותם כמה פעמים ולהגיע עם קביים. תודה לכולכם על זמנכם, מזל טוב ומצב רוח טוב. ) נ.ב: ביקורת, טוב ורע, כמו גם שאלות יתקבלו בברכה. )))