Har bir dasturchi dastlab kelajakdagi ishning sxemasi/rejasi/arxitekturasi haqida o'ylashi kerak, aks holda hammasi tartibsizlikka, to'liq anarxiyaga olib keladi. Har qanday postda bo'lgani kabi, dastlab sizga reja kerak, keling, boshlaylik.
1) Yangi boshlanuvchilar uchun Merge sort mavzusini olaylik.
2) Biz arxitektura va keyingi ish rejasini tuzamiz.
3) Biz rejaning barcha qismlarini ishlab chiqamiz va tavsiflaymiz.
4) Keling, ishlash va sifatni tekshiramiz.
2.1) Birlashtirish saralash nima.
2.2) Mumkin bo'lgan imzolarning tavsifi.
2.3) Misol keltiring.
2.4) Java tilidagi amalga oshirishni misol yordamida tasvirlab bering.
2.5) Har qanday qo'shimcha.
Birlashtirish - Java-da tartiblash
"Bo'l va zabt et" tamoyilini nazarda tutadi. G'oya va uning ma'nosi nima?
Tartiblash.
Massivni 1 elementga teng bo'lguncha qismlarga ajratamiz. Har bir 1 element tartiblangan.
Birlashish.
Saralangan elementlarni birlashtirish.
Ikki qavatli kartalar printsipiga asoslanadi. Biz stolga 2 ta kartani ularning qiymatlari yuqoriga ko'targan holda joylashtiramiz va eng past bo'lgan karta uchinchi kartalar to'plamiga joylashtiriladi. Oxir-oqibat, agar ma'lum bir palubadagi kartalar tugasa, biz ularni birma-bir hosil bo'lgan palubaga o'tkazamiz. Natijada ikkita tartiblangan massiv, bitta yangi, tartiblangan massiv birlashtiriladi.
Bu xuddi shu narsa, faqat indekslar bilan bog'liq. Ulardagi o'zgaruvchilar quyidagilardir:
A=Array= Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q +1- начало второго массива
r - конец второго массива
Agar bu o'zgaruvchilar tavsiflanmagan bo'lsa, unda bunday funktsiyani o'zi qilishni so'ragan kishi nima istayotganini bilmaydi. Va bu nima ekanligini bilish uchun siz Google-ni tekshirishingiz kerak bo'ladi, ehtimol siz uni topasiz. Keling, saralashimizga misol keltiraylik. Massiv bor {6, 1, 3, 5, 2, 4, 7, 8}, agar uning uzunligi 1 dan katta bo'lsa, unda biz uni 2 qismga ajratamiz va chap qismni {6, 1, 3, 5}va o'ng qismini olamiz {2, 4, 7, 8}. Uning uzunligi 1 dan katta bo'lguncha 2 qismga bo'lish amalini davom ettiramiz. Natijada uzunligi 1 elementga teng massivlar to'plamini olamiz, ya'ni: {6} {1} {3} {5} {2} {4} {7} {8}. Java-da amalga oshirish quyidagicha:
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);}
Keyin bu massivlarni 1 ga birlashtirishingiz kerak. Bu qanday amalga oshiriladi? Har bir massivni bir necha marta o'tkazmaslik uchun har bir massiv uchun pozitsiya indekslarini kiritamiz. Keyin bu ikki massiv yig'indisining uzunligiga teng bo'lgan tsikldan bir marta o'tamiz. Birinchi massivni va ikkinchi massivni oling va birinchi elementni oling, birinchi massivdagi 1-raqamli elementni va ikkinchi massivdagi 1-sonli elementni solishtiring ? Olingan massivga eng kichigi joylashtiriladi. Bu erda shunisi muhimki, agar biz birinchi massivdan element olgan bo'lsak, u holda tsikl o'tganda u birinchi massivning 2-elementiga va ikkinchi massivning 1-elementiga murojaat qilishi kerak. Buni amalga oshirish uchun siz ikkinchi massiv indeksini +1 ga oshirishingiz va tekshirishda birinchi massiv uchun xuddi shunday tsikl raqamidan ayirishingiz kerak. Nima uchun buni qilish kerakligi aniqmi? Yoki hech narsa aniq emasmi? :-) Masalan, 2 ta massiv bor: {1}{4}{8}va {3}{6}{7} sikl bor:
for(int i =0; i < arrayA.length + arrayB.length; i++){if(arrayA[i]< arrayB[i]){
arrayC[i]= arrayA[i];}else{
arrayC[i]= arrayB[i];}}
Loopning birinchi o'tishida shunday bo'ladi arrayC[1] = {1}: biz ushbu elementni birinchi massivdan oldik. Keyin, ikkinchi tsikldan o'tayotganda, biz allaqachon elementni solishtirishimiz kerak {4}va {3}, lekin buning uchun biz ikkala massivning pozitsiya indekslarini va ofsetini hisobga olishimiz kerak, buning uchun biz ularni kiritamiz.
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++;}}
Ammo bu hammasi emas, ba'zi massivlar avvalroq tugashi mumkinligini hisobga olishingiz kerak. Misol uchun, 3 ta massiv bor: {1}{3}{5}va {6}{7}{9} birinchi massiv ikkinchisi kelguncha tugaydi, buning uchun chekni kiritishingiz kerak va, qoida tariqasida, birlashtirish funktsiyasi tayyor.
Bu tartiblashda eng qiyin narsa bu rekursiyaga o'tish tamoyilidir. Bular. biz chap tomonni 2 ga bo'linmaguncha rekursiyaga tashlaymiz va keyin uni qayta ochamiz, so'z bilan aytganda, bu juda murakkab va chalkash, lekin tasavvur qilishga harakat qilganingizda, agar u hali aniq bo'lmasa, unda bu butunlay tartibsizlikdir. Keling, massivni olaylik: {2}{1}{4}{3}. Birinchi tartiblash rekursiyasi uni 2 qismga ajratadi va funksiyani yana 2-1 elementlari bilan , keyin yana 2 va 1 elementlari bilan ishga tushiradi , ularni navbatma-navbat qaytaradi, shuning uchun ular avval birlashma funksiyasiga kiradi va 1-2 keladi. tashqariga , keyin rekursiya qaytib qaytib , birlashma ichiga 4-3 tashlaydi , keyin 4 va 3 , keyin birlashma 3-4 qaytadi , va faqat keyin rekursiya yana qaytib aylanadi va 1-2 va 3-4 bo'ladi. birlashtirishga kiritiladi va tartiblangan qator 1-2-3-4 qaytariladi . Xo'sh, hammasi shunday, saralash ikkita funktsiyadan iborat.
sortArray(array);// кладем массив который нужно отсортироватьmergeArray(arrayA, arrayB);// кладем 2 массива которые нужно слить в один
Agar siz biron bir asosiy narsani yozsangiz, siz quyidagi kabi narsalarni olasiz:
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]+" ");}}
Men uchun bu saralash butunlay muvaffaqiyatsiz bo'ldi, millionlab savollar bor edi, lekin javoblar yo'q edi, men butun Internetni qazib oldim, qayta o'qidim, bir nechta videolarni tomosha qildim, lekin har doimgidek javoblarni faqat o'zim topdim. Va faqat men hamma joyda miltillovchidan mutlaqo farq qiladigan yechim yozishni boshlaganimda) Ammo oxir-oqibat u boshqalarga o'xshash bo'lib chiqdi))) Saralash aslida eng oddiy, asosiysi uni interaktiv tarzda amalda taqdim etish va hamma narsa o'z joyiga tushadi, agar o'zing o'ylab topsang, men video tayyorlayman)))) Hozircha menda shular kifoya qildi: Birlashtirish saralash Birlashtirish-tartiblash Eng muhimi, har doim undan reja tuzish boshi. Biror ishni boshlashdan oldin biroz kutib, o‘ylab ko‘rgan ma’qul. Bu ko'proq vaqt talab qilishi mumkin, lekin uni bir necha marta qayta yozish va tayoqchalar bilan chiqish kerak emas, balki tushunish va yechim paydo bo'ladi. Vaqtingiz uchun barchangizga rahmat, omad va yaxshi kayfiyat. ) PS: Tanqid, yaxshi va yomon, shuningdek, savollar juda yoqimli. )))
GO TO FULL VERSION