Hər bir proqramçı əvvəlcə gələcək işin sxemi/planı/arxitekturası üzərində düşünməlidir, əks halda hər şey qarışıqlıqla, tam anarxiya ilə başa çatır. Hər hansı bir yazıda olduğu kimi, əvvəlcə bir plana ehtiyacınız var, başlayaq.
1) Gəlin yeni başlayanlar üçün Merge sort mövzusunu götürək.
2) Arxitektura və gələcək işlərin planını yaradacağıq.
3) Planın bütün hissələri üzərində işləyəcəyik və təsvir edəcəyik.
4) Performans və keyfiyyəti yoxlayaq.
2.1) Merge çeşidləmə nədir.
2.2) Mümkün imzaların təsviri.
2.3) Nümunə verin.
2.4) Nümunədən istifadə edərək Java-da tətbiqi təsvir edin.
2.5) Əlavə hər şey.
Merge - Java-da çeşidləmə
“Parçala və qalib gəl” prinsipini nəzərdə tutur. İdeya nədir və onun mənası nədir?
Çeşidləmə.
Massivi 1 elementə bərabər olana qədər hissələrə bölürük. Hər 1 element sıralanır.
Birləşmə.
Sıralanmış elementlərin birləşdirilməsi.
Kartların iki göyərtəsi prinsipinə əsaslanır. 2 göyərtə kartlarını dəyərləri yuxarı olan masaya qoyuruq və ən aşağı olan kart üçüncü kart yığınına yerləşdirilir. Nəhayət, müəyyən bir göyərtədə kartlarımız tükənərsə, onları bir-bir nəticədə meydana gələn göyərtəyə köçürürük. Nəticə iki çeşidlənmiş massiv, bir yeni, çeşidlənmiş massivdən ibarət olacaq.
Bu, təxminən eyni şeydir, yalnız indekslərlə əlaqələndirilir. Onlardakı dəyişənlər bunlardır:
A=Array= Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q +1- начало второго массива
r - конец второго массива
Əgər bu dəyişənlər təsvir olunmursa, o zaman belə bir funksiyanı yerinə yetirməyi xahiş edən özü nə istədiyini bilmir. Və bunun nə olduğunu öyrənmək üçün Google-a göz atmalı olacaqsınız, yəqin ki, tapa bilərsiniz. Çeşidləməmizə bir misal verək. Massiv var , əgər onun uzunluğu 1-dən böyükdürsə, onu 2 hissəyə bölüb sol hissəni və sağ hissəsini {6, 1, 3, 5, 2, 4, 7, 8}alırıq . Onun uzunluğu 1-dən böyük olana qədər 2 hissəyə bölmək hərəkətini davam etdiririk.Nəticədə uzunluğu 1 element olan massivlər dəstəsi alırıq, yəni: . Java-da tətbiq belə bir şeydir: {6, 1, 3, 5}{2, 4, 7, 8}{6} {1} {3} {5} {2} {4} {7} {8}
publicint[]sortArray(int[] arrayA){// sorting Массива который передается в функцию// проверяем не нулевой ли он?if(arrayA ==null){returnnull;}// проверяем не 1 ли элемент в массиве?if(arrayA.length <2){return arrayA;// возврат в рекурсию в строки ниже см комменты.}// копируем левую часть от начала до серединыint[] arrayB =newint[arrayA.length /2];System.arraycopy(arrayA,0, arrayB,0, arrayA.length /2);// копируем правую часть от середины до конца массива, вычитаем из длины первую частьint[] arrayC =newint[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;// далее опять рекурсия возврата слияния двух отсортированных массивовreturnmergeArray(arrayB, arrayC);}
Sonra bu massivləri 1-ə birləşdirməlisiniz. Bu necə edilir? Hər massivdən bir neçə dəfə keçməmək üçün hər massiv üçün mövqe indekslərini daxil edək. Sonra bu iki massivin cəminin uzunluğuna bərabər olan bir döngədən bir dəfə keçəcəyik. Birinci massivi və ikinci massivi götürün və birinci elementi götürün, birinci massivdəki 1 nömrəli elementi və ikinci massivdəki 1 nömrəli elementi müqayisə edin ? Daha kiçik olanı yaranan massivdə yerləşdirilir. Burada vacibdir ki, əgər birinci massivdən element götürmüşdüksə, onda dövrə keçəndə o, birinci massivin 2-ci elementinə, ikinci massivin 1-ci elementinə istinad etməlidir. Bunu etmək üçün ikinci massivin indeksini +1 artırmalı və yoxlayarkən birinci massiv üçün olduğu kimi onu dövr nömrəsindən çıxarmalısınız. Bunu niyə etmək aydındırmı? Yoxsa heç nə aydın deyil? :-) Məsələn, 2 massiv var: {1}{4}{8}və {3}{6}{7} bir dövr var:
for(int i =0; i < arrayA.length + arrayB.length; i++){if(arrayA[i]< arrayB[i]){
arrayC[i]= arrayA[i];}else{
arrayC[i]= arrayB[i];}}
Döngənin ilk keçidində belə çıxır ki arrayC[1] = {1}: biz bu elementi birinci massivdən götürdük. Sonra, ikinci döngədən keçərkən, biz artıq elementi müqayisə etməliyik {4}və {3}, lakin bunun üçün mövqe indekslərini və hər iki massivin ofsetini nəzərə almalıyıq, bunun üçün onları daxil edirik.
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++;}}
Ancaq bu hamısı deyil, bəzi massivin daha əvvəl bitə biləcəyini nəzərə almaq lazımdır. Məsələn, 3 massiv var: {1}{3}{5}və {6}{7}{9} birinci massiv ikincisi gələnə qədər bitəcək, bunun üçün çek daxil etməlisiniz və prinsipcə birləşmə funksiyası hazırdır.
Bu çeşidləmə ilə bağlı ən çətin şey rekursiyaya keçid prinsipidir. Bunlar. sol tərəfi 2-yə bölünənə qədər rekursiyaya atırıq və sonra onu geri açırıq, sözlə bu, çox mürəkkəb və qarışıqdır, ancaq təsəvvür etməyə çalışdığınız zaman, hələ aydın deyilsə, bu, tam bir qarışıqlıqdır. Massivi götürək: {2}{1}{4}{3}. Birinci çeşidləmə rekursiyası onu 2 hissəyə böləcək və funksiyanı yenidən 2-1 elementləri ilə, sonra yenidən 2 və 1 elementləri ilə işlədəcək , onları növbə ilə qaytaracaq, beləliklə, onlar əvvəlcə birləşmə funksiyasına daxil olacaqlar və 1-2 gələcək. sonra rekursiya geri qayıdacaq və birləşməyə 4-3 , sonra 4 və 3 atacaq, bundan sonra birləşmə 3-4 qaytaracaq və yalnız bundan sonra rekursiya yenidən açılacaq və 1-2 və 3-4 olacaq. birləşməyə daxil edilir və çeşidlənmiş massiv 1-2-3-4 qaytarılacaq . Bəli, hamısı budur, çeşidləmə iki funksiyadan ibarətdir.
sortArray(array);// кладем массив который нужно отсортироватьmergeArray(arrayA, arrayB);// кладем 2 массива которые нужно слить в один
Bir növ əsas yazsanız, belə bir şey əldə edəcəksiniz:
publicstaticvoidmain(String[] args){Merge testMerge =newMerge();int[] result = testMerge.sortArray(newint[]{2,3,1,4});for(int i =0; i < result.length ; i++){System.out.print(result[i]+" ");}}
Mənim üçün bu çeşidləmə tamamilə uğursuz oldu, milyonlarla sual var idi, amma cavablar yox idi, mən bütün İnterneti qazdım, yenidən oxudum, bir dəstə videoya baxdım, amma həmişə olduğu kimi, cavabları yalnız özüm tapdım. Və yalnız hər yerdə yanıb-sönəndən tamamilə fərqli bir həll yazmağa başlayanda) Amma sonda o, bütün digərlərinə bənzədi))) Çeşidləmə əslində ən sadədir, əsas odur ki, onu interaktiv şəkildə hərəkətdə təqdim edək və başa düşsən hər şey öz yerinə düşür, mən video çəkəcəm)))) İndiyə qədər mənim üçün kifayət olan şeylər bunlardır: Birləşdirmə çeşidi Birləşdirin-çeşidləmə Ən vacibi həmişə bir plan qurmaqdır. Başlanğıc. Bir şey etməyə başlamazdan əvvəl bir az gözləmək və düşünmək daha yaxşıdır. Bu, daha çox vaxt apara bilər, amma bir neçə dəfə yenidən yazmaq və qoltuq dəyənəyi ilə gəlmək əvəzinə bir anlayış və həll ortaya çıxacaq. Vaxtınız, uğurlarınız və yaxşı əhval-ruhiyyəniz üçün hamınıza təşəkkür edirəm. ) PS: Tənqid, yaxşı və pis, eləcə də suallar çox xoşdur. )))
GO TO FULL VERSION