ผสานการเรียงลำดับใน Java

โปรแกรมเมอร์ทุกคนจะต้องคิดโครงร่าง/แผนงาน/สถาปัตยกรรมของงานในอนาคตตั้งแต่แรก ไม่เช่นนั้นทุกอย่างจะยุ่งวุ่นวายและเกิดอนาธิปไตยโดยสิ้นเชิง เช่นเดียวกับโพสต์ใดๆ ในตอนแรกคุณต้องมีแผน มาเริ่มกันเลย

• 1) มาดูหัวข้อการเรียงลำดับแบบผสานสำหรับผู้เริ่มต้นกันดีกว่า
• 2) เราจะสร้างสถาปัตยกรรมและแผนงานต่อไป
• 3) เราจะดำเนินการและอธิบายทุกส่วนของแผน
• 4) มาตรวจสอบประสิทธิภาพและคุณภาพกันดีกว่า

• 2.1) การเรียงลำดับแบบผสานคืออะไร
• 2.2) คำอธิบายของลายเซ็นที่เป็นไปได้
• 2.3) ให้ตัวอย่าง.
• 2.4) อธิบายการใช้งานใน Java โดยใช้ตัวอย่าง
• 2.5) สิ่งพิเศษใดๆ

ผสาน - ผสานการเรียงลำดับใน Java

แสดงถึงหลักการ "แบ่งแยกและพิชิต" แนวคิดและความหมายของมันคืออะไร?

1. การเรียงลำดับ

   เราแบ่งอาร์เรย์ออกเป็นส่วน ๆ จนกว่าจะเท่ากับ 1 องค์ประกอบ ทุกๆ 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 - конец второго массива

หากไม่ได้อธิบายตัวแปรเหล่านี้แสดงว่าผู้ที่ขอให้สร้างฟังก์ชันดังกล่าวจะไม่รู้ว่าเขาต้องการอะไร และคุณจะต้องค้นหา Google เพื่อดูว่ามันคืออะไร คุณอาจจะพบมันก็ได้ ลองยกตัวอย่างการเรียงลำดับของเรา มีอาร์เรย์{6, 1, 3, 5, 2, 4, 7, 8}หากความยาวของมันมากกว่า 1 เราจะแบ่งออกเป็น 2 ส่วนและรับส่วนด้านซ้าย{6, 1, 3, 5}และส่วนด้านขวา{2, 4, 7, 8}. เราดำเนินการแบ่งออกเป็น 2 ส่วนต่อไปจนกระทั่งมีความยาวมากกว่า 1 ด้วยเหตุนี้เราจึงได้อาร์เรย์จำนวนหนึ่งที่มีความยาว 1 องค์ประกอบ กล่าวคือ{6} {1} {3} {5} {2} {4} {7} {8}: การใช้งานใน Java มีลักษณะดังนี้:

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] + " ");
        }
    }

สำหรับฉัน การเรียงลำดับนี้ล้มเหลวโดยสิ้นเชิง มีคำถามเป็นล้านข้อ แต่ไม่มีคำตอบ ฉันค้นหาผ่านอินเทอร์เน็ต อ่านซ้ำ ดูวิดีโอมากมาย แต่เช่นเคย ฉันพบเพียงคำตอบด้วยตัวเองเท่านั้น และเมื่อฉันเริ่มเขียนวิธีแก้ปัญหาที่แตกต่างไปจากที่แฟลชทุกที่) แต่สุดท้ายมันก็คล้ายกับวิธีอื่น ๆ ทั้งหมด))) การเรียงลำดับเป็นวิธีที่ง่ายที่สุดจริง ๆ สิ่งสำคัญคือการนำเสนอแบบโต้ตอบในการดำเนินการและ ทุกอย่างเข้าที่ถ้าคุณเข้าใจ ฉันจะทำวิดีโอ)))) จนถึงตอนนี้ นั่นคือทั้งหมดที่ฉันพอสำหรับ: ผสานการเรียงลำดับ ผสานการเรียงลำดับ สิ่งที่สำคัญที่สุดคือการวางแผนจากเสมอ การเริ่มต้น. ดีกว่าที่จะรอสักนิดและคิดก่อนที่จะเริ่มทำอะไร อาจต้องใช้เวลามากกว่านี้ แต่ความเข้าใจและวิธีแก้ปัญหาจะปรากฏขึ้น แทนที่จะต้องเขียนซ้ำสองสามครั้งแล้วใช้ไม้ค้ำยัน ขอขอบคุณทุกท่านที่สละเวลา ขอให้โชคดี และอารมณ์ดี ) ป.ล. ยินดีรับคำติชมทั้งดีและไม่ดีตลอดจนคำถาม )))