Pagsamahin-uri-uriin sa Java

Dapat munang isipin ng bawat programmer ang scheme/plano/arkitektura ng trabaho sa hinaharap, kung hindi, magtatapos ang lahat sa gulo, na may kumpletong anarkiya. Tulad ng anumang post, kailangan mo muna ng plano, magsimula tayo.

• 1) Kunin natin ang paksa ng Merge sort para sa mga nagsisimula.
• 2) Gagawa kami ng isang arkitektura at isang plano para sa karagdagang trabaho.
• 3) Aayusin at ilalarawan namin ang lahat ng bahagi ng plano.
• 4) Suriin natin ang pagganap at kalidad.

• 2.1) Ano ang pag-uuri ng Merge.
• 2.2) Paglalarawan ng mga posibleng lagda.
• 2.3) Magbigay ng halimbawa.
• 2.4) Ilarawan ang pagpapatupad sa Java gamit ang isang halimbawa.
• 2.5) Anumang dagdag.

Pagsamahin - pagsamahin ang pag-uuri sa Java

Nagpapahiwatig ng prinsipyo ng "hatiin at lupigin". Ano ang ideya at kahulugan nito?

1. Pag-uuri.

   Hinahati namin ang array sa mga bahagi hanggang sa ito ay katumbas ng 1 elemento. Pinagbukod-bukod ang bawat 1 elemento.

2. Pagsama-sama.

   Pinagsasama-sama ang pinagsunod-sunod na mga elemento.
   Batay sa prinsipyo ng dalawang deck ng mga baraha. Naglalagay kami ng 2 deck ng mga card sa mesa na ang kanilang mga halaga ay nakataas, at ang card na pinakamababa ay inilalagay sa ikatlong resultang tumpok ng mga card. Sa huli, kung maubusan kami ng mga card sa isang partikular na deck, inililipat namin ang mga ito nang paisa-isa sa resultang deck. Ang resulta ay isang pinagsamang dalawang pinagsunod-sunod na array, isang bago, pinagsunod-sunod na array.

Ang oras na ginugol ay O(n log2 n). Ang pag-uuri ay itinuturing na medyo mabilis. Sa madaling sabi tungkol sa algorithmic complexity, kung kailangan ito ng sinuman. Madalas mong makikita ang mga function tulad ng:

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

Ito ay tungkol sa parehong bagay, naka-link lamang sa mga index. Ang mga variable sa kanila ay:

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

Kung ang mga variable na ito ay hindi inilarawan, kung gayon ang humihiling na gumawa ng ganoong function mismo ay hindi alam kung ano ang gusto niya. At kailangan mong saliksikin ang Google para malaman kung ano ito, malamang na mahahanap mo ito, marahil. Magbigay tayo ng halimbawa ng ating pag-uuri. Mayroong isang array {6, 1, 3, 5, 2, 4, 7, 8}, kung ang haba nito ay mas malaki kaysa sa 1, pagkatapos ay hatiin natin ito sa 2 bahagi at makuha ang kaliwang bahagi {6, 1, 3, 5}at kanang bahagi {2, 4, 7, 8}. Ipinagpapatuloy namin ang pagkilos ng paghahati sa 2 bahagi hanggang sa ang haba nito ay mas malaki sa 1. Bilang resulta, nakakakuha kami ng isang grupo ng mga array na may haba na 1 elemento, katulad ng: {6} {1} {3} {5} {2} {4} {7} {8}. Ang pagpapatupad sa Java ay katulad nito:

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);
    }

Susunod na kailangan mong pagsamahin ang mga arrays na ito sa 1. Paano ito ginagawa? Upang maiwasang dumaan sa bawat array nang maraming beses, ilagay natin ang mga indeks ng posisyon para sa bawat array. Pagkatapos ay dadaan tayo sa isang loop nang isang beses, katumbas ng haba ng kabuuan ng dalawang array na ito. Kunin ang unang array at ang pangalawang array, at kunin ang unang elemento, ihambing ang element number 1 sa unang array at element number 1 sa pangalawang array ? Ang mas maliit ay inilalagay sa resultang array. Mahalaga dito na kung kukuha tayo ng elemento mula sa unang array, pagkatapos ay kapag pumasa ang loop, dapat itong sumangguni sa 2nd element ng unang array at sa 1st element ng pangalawang array. Upang gawin ito, kailangan mong taasan ang index ng pangalawang array sa pamamagitan ng +1 at, kapag sinusuri, ibawas ito mula sa numero ng cycle, katulad din para sa unang array. Malinaw ba kung bakit gagawin ito? O wala talagang malinaw? :-) Halimbawa, mayroong 2 array: {1}{4}{8}at {3}{6}{7} At mayroong isang cycle:

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

Sa unang pass ng loop, lumalabas na arrayC[1] = {1}: kinuha namin ang elementong ito mula sa unang array. Pagkatapos, kapag dumaan sa pangalawang loop, kailangan na nating ihambing ang elemento {4}at {3}, ngunit upang magawa ito kailangan nating isaalang-alang ang mga indeks ng posisyon at ang offset ng parehong mga array, para dito ipinasok natin ang mga ito.

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++;
	}
}

Ngunit hindi lang iyon, kailangan mong isaalang-alang na ang ilang array ay maaaring magtapos nang mas maaga. Halimbawa, mayroong 3 array: {1}{3}{5}at {6}{7}{9} Ang unang array ay magtatapos bago dumating ang pangalawa, para dito kailangan mong magpasok ng tseke at, sa prinsipyo, handa na ang merge function.

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;

Ang pinakamahirap na bagay tungkol sa pag-uuri na ito ay ang prinsipyo ng recursion transition. Yung. itinatapon namin ang kaliwang bahagi sa recursion hanggang sa ito ay mahahati sa 2, at pagkatapos ay i-unwind ito pabalik, sa mga salita ito ay napaka-kumplikado at nakakalito, ngunit kapag sinubukan mong isipin, kung ito ay hindi pa malinaw, kung gayon ito ay isang kumpletong gulo. Kunin natin ang array: {2}{1}{4}{3}. Ang unang pag-uuri ng recursion ay hahatiin ito sa 2 bahagi at patakbuhin muli ang function na may mga elemento 2-1 , pagkatapos ay muli sa mga elemento 2 at 1 , ibalik ang mga ito sa turn, upang makapasok muna sila sa merge function, at 1-2 ay darating out , pagkatapos ay babalik ang recursion at itatapon ang 4-3 sa merge , pagkatapos ay 4 at 3 , pagkatapos nito ay babalik ang merge 3-4 , at pagkatapos lamang ay mag-unwind muli ang recursion at ang 1-2 at 3-4 ay magiging kasama sa pagsasanib , at ang pinagsunod-sunod na hanay ay ibabalik sa 1-2-3-4 . Well, iyon lang, ang pag-uuri ay binubuo ng dalawang function.

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

Kung isusulat mo ang ilang uri ng pangunahing, makakakuha ka ng isang bagay tulad ng:

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

Para sa akin, ang pag-uuri na ito ay isang kumpletong kabiguan, mayroong isang milyong mga katanungan, ngunit walang mga sagot, naghukay ako sa buong Internet, muling nagbasa, nanood ng isang bungkos ng mga video, ngunit tulad ng dati, natagpuan ko lamang ang mga sagot sa aking sarili. At noong nagsimula akong magsulat ng isang solusyon na ganap na naiiba mula sa isa na kumikislap sa lahat ng dako) Ngunit sa huli ito ay naging katulad ng lahat ng iba pa))) Ang pag-uuri ay talagang pinakasimpleng, ang pangunahing bagay ay upang ipakita ito nang interactive sa aksyon, at everything falls into place if you get the hang of it, gagawa ako ng video)))) So far, yun lang ang meron ako para sa: Merge sort Merge-sort Ang pinakamahalagang bagay ay laging gumawa ng plano mula sa ang simula. Mas mabuting maghintay ng kaunti at mag-isip bago ka magsimulang gumawa ng anuman. Maaaring tumagal ng mas maraming oras, ngunit lilitaw ang isang pag-unawa at isang solusyon sa halip na muling isulat ito ng ilang beses at makabuo ng mga saklay. Salamat sa lahat para sa iyong oras, good luck at magandang kalooban. ) PS: Ang kritisismo, mabuti at masama, pati na rin ang mga tanong ay malugod na tinatanggap. )))