Nangungunang Mga Istraktura ng Data at Algorithm sa Java Na Kailangan Mong Malaman

Ang blog na ito sa Mga Istraktura ng Data at Mga Algorithm sa Java ay makakatulong sa iyo na maunawaan ang lahat ng mga pangunahing istraktura ng data at mga algorithm sa Java.

Kung pipiliin ko ang nag-iisang pinakamahalagang paksa sa pag-unlad ng software, ito ay ang mga istruktura ng data at algorithm. Maaari mong isipin ito bilang pangunahing tool na magagamit sa bawat programmer ng computer. Habang nagprogram, ginagamit namin mga istruktura ng data upang maiimbak at ayusin ang data, at mga algorithm upang manipulahin ang data sa mga istrukturang iyon. Naglalaman ang artikulong ito ng isang detalyadong pagsusuri ng lahat ng mga karaniwang istraktura ng data at mga algorithm sa upang payagan ang mga mambabasa na maging mahusay sa gamit.

Nakalista sa ibaba ang mga paksang tinalakay sa artikulong ito:





Mga Istruktura ng Data sa Java

Ang isang istraktura ng data ay isang paraan ng pag-iimbak at pag-aayos ng data sa isang computer upang magamit ito nang mahusay. Nagbibigay ito ng isang paraan upang pamahalaan nang mahusay ang maraming data. At ang mahusay na mga istraktura ng data ay susi sa pagdidisenyo ng mahusay na mga algorithm.

Saang artikulong 'Mga Istraktura at Algorithm ng Data sa Java' na artikulong ito, sasakupin namin ang mga pangunahing istruktura ng data tulad ng:



Suriin natin ang bawat isa sa kanila.

Mga Linear Data Structure sa Java

Mga linyang istraktura ng data sa ay ang mga ang mga elemento ay sunud-sunod at nakaayos sa isang paraan upang: mayroon lamang isa unang elemento at may isa lamang susunod na elemento , isa lang yan huling elemento at may isa lamang nakaraang elemento , habang ang lahat ng iba pang mga elemento ay may a susunod na at a dati elemento.

Mga array

Isang array ay isang linear na istraktura ng datana kumakatawan sa isang pangkat ng mga katulad na elemento, na na-access sa pamamagitan ng index. Dapat ibigay ang laki ng isang array bago itago ang data. Nakalista sa ibaba ang mga katangian ng isang array:



  • Ang bawat elemento sa isang array ay pareho ng uri ng data at may parehong laki
  • Ang mga elemento ng array ay nakaimbak sa magkadikit na lokasyon ng memorya na may unang elemento ay nagsisimula sa pinakamaliit na lokasyon ng memorya
  • Ang mga elemento ng array ay maaaring ma-access nang random
  • Ang istraktura ng data ng array ay hindi ganap na pabago-bago

Mga array - Edureka

Halimbawa , baka gusto natin ng isang video game na subaybayan ang nangungunang sampung mga marka para sa larong iyon. Kaysa gumamit ng sampung iba variable para sa gawaing ito, maaari naming gamitin ang isang solong pangalan para sa buong pangkat at gumamit ng mga numero ng index upang mag-refer sa mga mataas na marka sa pangkat na iyon.

Listahan ng naka-link

SA ay isang linear na istraktura ng data na may koleksyon ng maraming mga node, kung saan eNag-iimbak ang elemento ng ach ng sarili nitong data at isang pointer sa lokasyon ng susunod na elemento. Ang huling link sa isang naka-link na listahan ay tumuturo sa null, na nagpapahiwatig ng pagtatapos ng kadena. Ang isang elemento sa isang naka-link na listahan ay tinatawag na a node . Ang unang node ay tinawag na ulo .Ang huling node ay tinawagang buntot .

Mga uri ng Listahan ng Naka-link

Listahan ng Nai-link na Mag-isa (Uni-Directional)

Dobleng Listahang Nakaugnay (Bi-Directional)

Listahan ng Naka-link na Paikot

Narito ang isang simpleng halimbawa: Pag-isipan ang isang naka-link na listahan tulad ng isang kadena ng mga paperclips na naka-link nang magkasama. Madali kang makakapagdagdag ng isa pang paperclip sa itaas o ibaba. Mabilis pa itong magpasok ng isa sa gitna. Ang kailangan mo lang gawin ay idiskonekta lamang ang kadena sa gitna, idagdag ang bagong paperclip, pagkatapos ay ikonekta muli ang iba pang kalahati. Ang isang naka-link na listahan ay pareho.

Stack

Stack, isang abstract na istraktura ng data, ay isang koleksyon ng mga bagay na ipinasok at tinanggal alinsunod sa last-in-first-out (LIFO) prinsipyo. Ang mga bagay ay maaaring ipasok sa isang stack sa anumang punto ng oras, ngunit ang pinakabagong lamang na naipasok (iyon ay, 'huling') bagay na maaaring alisin sa anumang oras.Nakalista sa ibaba ang mga katangian ng isang stack:

  • Ito ay isang listahan ng orderd kung saanang pagpasok at pagtanggal ay maaaring gumanap lamang sa isang dulo na tinatawag na tuktok
  • Recursive data istraktura na may isang pointer sa tuktok na elemento
  • Sinusunod ang last-in-first-out (LIFO) prinsipyo
  • Sinusuportahan ang dalawang pinaka-pangunahing pamamaraan
    • itulak (e): Ipasok ang elemento e, sa tuktok ng stack
    • pop (): Alisin at ibalik ang nangungunang elemento sa stack

Ang mga praktikal na halimbawa ng stack ay kasama kapag binabaligtad ang isang salita,upang suriin ang kawastuhan ng panaklongpagkakasunud-sunod,pagpapatupad ng pabalik na pag-andar sa mga browser at marami pa.

Pila

ay isa ring uri ng abstract na istraktura ng data. Hindi tulad ng isang stack, ang pila ay isang koleksyon ng mga bagay na naipasok at inalis ayon sa first-in-first-out (FIFO) prinsipyo. Iyon ay, ang mga elemento ay maaaring ipasok sa anumang punto ng oras, ngunit ang elemento lamang na pinakamahaba sa pila ang maaaring alisin sa anumang oras.Nakalista sa ibaba ang mga katangian ng isang pila:

  • Kadalasang tinutukoy bilang ang first-in-first-out listahan
  • Sinusuportahan ang dalawang pinaka-pangunahing pamamaraan
    • enqueue (e): Ipasok ang elemento e, sa likuran ng pila
    • dequeue (): Alisin at ibalik ang elemento mula sa sa harap ng pila

Ginagamit ang mga pila sahindi magkasabay na paglipat ng data sa pagitan ng dalawang proseso, pag-iiskedyul ng CPU, Pag-iskedyul ng Disk at iba pang mga sitwasyon kung saan ibinabahagi ang mga mapagkukunan sa maraming mga gumagamit at nagsilbi sa unang unang batayan ng server. Susunod sa artikulong 'Mga Istraktura ng Data at Algorithm sa Java' na artikulong ito, mayroon kaming mga hierarchical na istraktura ng data.

Mga Hierarchical Data Structure sa Java

Punong Binary

Ang Binary Tree ay isangmga istraktura ng data ng hierarchical tree kung saan ang bawat node ay mayroong higit sa dalawang anak , na tinukoy bilang ang kaliwang anak at ang tamang anak . Ang bawat puno ng binary ay may mga sumusunod na pangkat ng mga node:

  • Root Node: Ito ang pinakamataas na node at madalas na tinutukoy bilang pangunahing nodedahil ang lahat ng iba pang mga node ay maaaring maabot mula sa ugat
  • Kaliwa Sub-Tree, na isa ring binary tree
  • Tamang Sub-Tree, na isa ring binary tree

Nakalista sa ibaba ang mga pag-aari ng isang puno ng binary:

  • Ang isang puno ng binary ay maaaring daanan sa dalawang paraan:
    • Lalim ng Unang Traversal : In-order (Kaliwa-Root-Kanan), Preorder (Root-Left-Right) at Postorder (Left-Right-Root)
    • Breadth First Traversal : Antas ng Traversal ng Order
  • Pagkumplikado ng Oras ng Tree Traversal: O (n)
  • Ang maximum na bilang ng mga node sa antas na ā€˜lā€™ = 2l-1.

Ang mga aplikasyon ng mga puno ng binary ay kasama ang:

  • Ginamit sa maraming mga application sa paghahanap kung saan ang data ay patuloy na pumapasok / umaalis
  • Bilang isang daloy ng trabaho para sa pagsasama ng mga digital na imahe para sa mga visual effects
  • Ginamit sa halos bawat router na may mataas na bandwidth para sa pag-iimbak ng mga talahanayan ng router
  • Ginamit din sa wireless networking at alokasyon ng memorya
  • Ginamit sa mga algorithm ng compression at marami pa

Binary Heap

Ang Binary Heap ay kumpletopuno ng binary, na sumasagot sa pagmamay-ari ng magbunton. Sa simpleng term na itoay isang pagkakaiba-iba ng isang puno ng binary na may mga sumusunod na katangian:

  • Ang heap ay isang kumpletong puno ng binary: Ang isang puno ay sinasabing kumpleto kung ang lahat ng antas nito, maliban sa posibleng pinakamalalim, ay kumpleto. Tang kanyang pag-aari ng Binary Heap ay ginagawang angkop na itago sa isang .
  • Sinusundan ang ari-arian ng magbunton: Ang isang Binary Heap ay alinman sa a Min-heap o a Max-Heap .
    • Min Binary Heap: Fo bawat node sa isang tambak, ang halaga ng node ay mas mababa sa o katumbas ng halaga ng mga bata
    • Max Binary Heap: Fo bawat node sa isang tambak, ang halaga ng node ay mas malaki kaysa sa o katumbas ng halaga ng mga bata

Kasama sa mga sikat na application ng binary heappagpapatupad ng mahusay na mga priyoridad na queues, mahusay na paghanap ng k pinakamaliit (o pinakamalaki) na mga elemento sa isang array at marami pa.

Mga Talahanayan ng Hash

Isipin na mayroon kang isang bagay at nais mong magtalaga ng isang susi dito upang gawing napakadali ng paghahanap. Upang maiimbak ang pares ng key / halaga na iyon, maaari kang gumamit ng isang simpleng array tulad ng isang istraktura ng data kung saan ang mga key (integers) ay maaaring direktang magamit bilang isang index upang mag-imbak ng mga halaga ng data. Gayunpaman, sa mga kaso kung saan ang mga key ay masyadong malaki at hindi maaaring gamitin nang direkta bilang isang index, isang diskarteng tinatawag na hashing ang ginagamit.

Sa pag-hash, ang malalaking mga susi ay ginawang maliit na mga susi sa pamamagitan ng paggamit pag-andar ng hash . Ang mga halaga ay pagkatapos ay nakaimbak sa isang istraktura ng data na tinatawagsa hash table. Ang isang talahanayan ng hash ay isang istraktura ng data na nagpapatupad ng isang ADT ng diksyonaryo, isang istrakturang maaaring mapa ang mga natatanging susi sa mga halaga.

Sa pangkalahatan, ang isang hash table ay may dalawang pangunahing sangkap:

  1. Bucket Array: Ang isang bucket array para sa isang hash table ay isang array A ng laki ng N, kung saan ang bawat cell ng A ay naisip bilang isang 'bucket', iyon ay, isang koleksyon ng mga pares ng key-halaga. Ang integer N ay tumutukoy sa kakayahan ng array.
  2. Hash Function: Ito ay anumang pagpapaandar na nagpapapa sa bawat key k sa aming mapa sa isang integer sa saklaw na [0, N & minus 1], kung saan ang N ay ang kapasidad ng bucket array para sa talahanayan na ito.

Kapag naglalagay kami ng mga bagay sa isang nai-tweet, posible na ang magkakaibang mga bagay ay maaaring magkaroon ng parehong hashcode. Tinawag itong a pagkakabanggaan . Upang harapin ang banggaan, may mga diskarteng tulad ng pag-chain at bukas na pagtugon.

Kaya, ito ang ilang pangunahing at pinaka-madalas na ginagamit na mga istraktura ng data sa Java. Ngayong may kamalayan ka sa bawat isa sa mga ito, maaari mong simulang ipatupad ang mga ito sa iyo . Sa pamamagitan nito, nakumpleto namin ang unang bahagi ng 'artikulong' Mga Istraktura at Algorithm ng Data sa Java 'na artikulong ito. Sa susunod na bahagi, malalaman natin ang tungkol sapangunahing mga algorithm at kung paano gamitin ang mga ito sa mga praktikal na aplikasyon tulad ng pag-uuri at paghahanap, hatiin at lupigin, sakim na mga algorithm, pabagu-bagong programa.

Mga algorithm sa Java

Ginamit ang makasaysayang bilang isang tool para sa paglutas ng mga kumplikadong pagkalkula sa matematika, ang mga algorithm ay malalim na nakakonekta sa computer science, at partikular na ang mga istruktura ng data. Ang isang algorithm ay isang pagkakasunud-sunod ng mga tagubilin na naglalarawan sa isang paraan ng paglutas ng isang tukoy na problema sa isang may hangganan na panahon. Kinakatawan ang mga ito sa dalawang paraan:

  • Mga Flowchart - Ito ay isangvisual na representasyon ng daloy ng kontrol ng isang algorithm
  • Pseudocode - Itoay isang representasyong pangkonteksto ng isang algorithm na tinatayang ang huling code ng mapagkukunan

Tandaan: Ang pagganap ng algorithm ay sinusukat batay sa pagiging kumplikado ng oras at pagiging kumplikado sa kalawakan. Kadalasan, ang pagiging kumplikado ng anumang algorithm ay nakasalalay sa problema at sa mismong algorithm.

Tuklasin natin ang dalawang pangunahing mga kategorya ng mga algorithm sa Java, na kung saan ay:

Pag-uuri ng Mga Algorithm sa Java

Ang pag-aayos ng mga algorithm ay mga algorithm na naglalagay ng mga elemento ng isang listahan sa isang tiyak na pagkakasunud-sunod. Ang pinakakaraniwang ginagamit na mga order ay ang pagkakasunud-sunod ng bilang at pagkakasunud-sunod ng leksikograpiko. Sa artikulong 'Mga Istraktura at Algorithm ng Data' na ito ay hinahayaan ang galugarin ang ilang mga pag-uuri ng mga algorithm.

ano pojo sa java

Pag-uuri ng Bubble sa Java

Ang Bubble Sort, na madalas na tinutukoy bilang paglubog ng uri, ay ang pinakasimpleng pag-uuri ng algorithm. Paulit-ulit nitong sinusundan ang listahan upang maiayos, ihinahambing ang bawat pares ng mga katabing elemento at ipinagpapalit kung nasa maling pagkakasunud-sunod ang mga ito.Ang uri ng bubble ay nakakuha ng pangalan dahil sinasala nito ang mga elemento sa tuktok ng array, tulad ng mga bula na lumulutang sa tubig.

Naritopseudocode na kumakatawan sa Bubble Sort Algorithm (pataas na konteksto ng pag-uuri).

ang isang [] ay isang hanay ng laki N simulan ang BubbleSort (a []) ideklara ang integer i, j para sa i = 0 hanggang N - 1 para sa j = 0 hanggang N - i - 1 kung isang [j]> a [j + 1 ] pagkatapos ay ipagpalit ang isang [j], isang [j + 1] na wakas kung magtatapos para ibalik ang isang dulo ng BubbleSort

Ang code na ito ay nag-order ng isang isang-dimensional na hanay ng mga item ng data ng N sa pataas na pagkakasunud-sunod. Ginagawa ng isang panlabas na loop ang N-1 na dumaan sa array. Ang bawat pass ay gumagamit ng isang panloob na loop upang makipagpalitan ng mga item ng data tulad ng susunod na pinakamaliit na item ng data na 'mga bula' patungo sa simula ng array. Ngunit ang problema ay kailangan ng algorithm ng isang buong pass nang walang anumang pagpapalit upang malaman na ang listahan ay pinagsunod-sunod.

Pinakamasamang at Karaniwan na Kakayahang Oras ng Kaso: O (n * n). Ang pinakapangit na kaso ay nangyayari kapag ang isang array ay nabaligtad na pinagsunod-sunod.

Pinakamahusay na Kakayahang Oras ng Kaso: O (n). Pinakamahusay na kaso ay nangyayari kapag ang isang array ay naayos na.

Pinili ng Pinili sa Java

Ang pag-uuri ng pagpipilian ay isang kumbinasyon ng parehong paghahanap at pag-uuri. Ang algorithm ay nag-uuri ng isang array sa pamamagitan ng paulit-ulit na paghahanap ng minimum na elemento (isinasaalang-alang ang pataas na pagkakasunud-sunod) mula sa hindi naayos na bahagi at inilalagay ito sa isang tamang posisyon sa array.

Narito ang pseudocode na kumakatawan sa Algorithm ng Pagsunud-sunod ng Seleksyon (pataas na konteksto ng pag-uuri).

ang isang [] ay isang hanay ng laki N simulan ang SelectionSort (isang []) para sa i = 0 hanggang n - 1 / * itakda ang kasalukuyang elemento bilang minimum * / min = i / * hanapin ang minimum na elemento * / para sa j = i + 1 sa n kung listahan [j]

Tulad ng maaari mong maunawaan mula sa code, ang bilang ng mga beses na ang uri ay dumadaan sa array ay isang mas mababa kaysa sa bilang ng mga item sa array. Mahahanap ng panloob na loop ang susunod na pinakamaliit na halaga at ang mga panlabas na lugar ng loop na nagkakahalaga sa tamang lokasyon nito. Ang pag-uuri ng pagpipilian ay hindi kailanman gumagawa ng higit sa O (n) swap at maaaring maging kapaki-pakinabang kapag ang pagsulat ng memorya ay isang magastos na operasyon.

Pagiging kumplikado ng Oras: O (n2) tulad ng may dalawang naka-pugad na mga loop.

Pantulong na Puwang: O (1).

Pagpasok Pagsunud-sunurin sa Java

Ang Pagpasok Pagbukud-bukurin ay isang simpleng pag-uuri algorithm na kung saan iterates sa pamamagitan ng listahan sa pamamagitan ng pag-ubos ng isang elemento ng pag-input nang paisa-isa at itinatayo ang huling pinagsunod-sunod na array. Napakadali at mas epektibo sa mas maliit na mga hanay ng data. Ito ay matatag at nasa lugar na pamamaraan ng pag-uuri.

Narito ang pseudocode na kumakatawan sa Insertion Sort Algorithm (pataas na konteksto ng pag-uuri).

ang isang [] ay isang hanay ng laki N simulang InsertionSort (isang []) para sa i = 1 hanggang N key = a [i] j = i - 1 habang (j> = 0 at isang [j]> key0 a [j + 1] = x [j] j = j - 1 dulo habang isang [j + 1] = key end para sa pagtatapos ng InsertionSort

Tulad ng naiintindihan mo mula sa code, ang pagsingit ng algorithm sa uriinaalis ang isang elemento mula sa data ng pag-input, hahanapin ang lokasyon na kabilang sa loob ng listahan ng pinagsunod-sunod at isingit doon. Umuulit ito hanggang sa walang mga elemento ng pag-input na mananatiling hindi naiayos.

Pinakamagandang kaso: Ang pinakamagandang kaso ay kapag ang input ay isang array na naayos na. Sa kasong ito ang uri ng pagpapasok ay may isang linear na tumatakbo na oras (ibig sabihin, & Theta (n)).

Pinakamasamang Kaso: Ang pinakasimpleng pinakamasamang input ng kaso ay isang array na pinagsunod-sunod sa reverse order.

QuickSort sa Java

Ang Quicksort algorithm ay isang mabilis, recursive, hindi matatag na pag-uuri ng algorithm na gumagana sa prinsipyo ng paghati at pagsakop. Pinipili nito ang isang elemento bilang pivot at ibinabahagi ang ibinigay na array sa paligid ng piniling pivot na iyon.

Mga hakbang upang ipatupad ang Mabilis na pag-uuri:

  1. Pumili ng angkop na 'pivot point'.
  2. Hatiin ang mga listahan sa dalawang listahanbatay sa elementong ito ng pivot. Ang bawat elemento na mas maliit kaysa sa elemento ng pivot ay inilalagay sa kaliwang listahan at ang bawat elemento na mas malaki ay inilalagay sa tamang listahan. Kung ang isang elemento ay katumbas ng elemento ng pivot maaari itong pumunta sa anumang listahan. Tinatawag itong operasyon ng pagkahati.
  3. Recursively pag-uri-uriin ang bawat isa sa mga mas maliit na listahan.

Narito ang pseudocode na kumakatawan sa Quicksort Algorithm.

QuickSort (Ang isang bilang array, mababa bilang int, mataas ng int) {kung (mababa

Sa itaas na pseudocode, pagkahati () gumaganap ang pagpapaandar sa operasyon ng pagkahati at Quicksort () paulit-ulit na tawagan ang pagpapaandar ng pagkahati para sa bawat mas maliit na nabuong listahan. Ang pagiging kumplikado ng quicksort sa average case ay ang & Theta (n log (n)) at sa pinakapangit na kaso ay ang & Theta (n2).

Pagsamahin ang Pagsunud-sunurin sa Java

Ang Mergesort ay isang mabilis, recursive, stable na pag-uuri ng algorithm na gumagana rin ng prinsipyo ng paghati at pagsakop. Katulad ng quicksort, pinaghahati-hati ng pag-uuri-uri ang listahan ng mga elemento sa dalawang listahan. Ang mga listahang ito ay pinagsunod-sunod na pinagsunod-sunod at pagkatapos ay pinagsama. Sa panahon ng pagsasama ng mga listahan, ang mga elemento ay ipinasok (o pinagsama) sa tamang lugar sa listahan.

Narito ang pseudocode na kumakatawan sa Merge Sort Algorithm.

pamamaraan MergeSort (isang bilang array) kung (n == 1) ibalik ang isang var l1 bilang array = a [0] ... isang [n / 2] var l2 bilang array = a [n / 2 + 1] ... isang [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) pagtatapos ng pamamaraan na pagsasama (a bilang array, b bilang array) var c bilang array habang (a at b may mga elemento) kung ( isang [0]> b [0]) idagdag ang b [0] sa dulo ng c alisin ang b [0] mula sa b magdagdag ng isang [0] sa dulo ng c alisin ang isang [0] mula sa isang dulo kung magtatapos habang habang (may mga elemento) magdagdag ng isang [0] sa dulo ng c alisin ang isang [0] mula sa isang dulo habang habang (b ay may mga elemento) idagdag ang b [0] sa dulo ng c alisin ang b [0] mula sa b dulo habang bumalik c pagtatapos ng pamamaraan

sumanib-uuri() Hinahati ng pagpapaandar ang listahan sa dalawa, mga tawag sumanib-uuri() sa mga listahang ito nang magkahiwalay at pagkatapos ay pinagsasama ang mga ito sa pamamagitan ng pagpapadala sa kanila bilang mga parameter upang pagsamahin () ang pagpapaandar.Ang algorithm ay may pagiging kumplikado ng O (n log (n)) at may malawak na hanay ng mga application.

Heap Sort sa Java

Ang Heapsort ay isang algorithm ng pag-uuri na batay sa paghahambingAng istraktura ng data ng Binary Heap. Maaari mong isipin ito bilang pinabuting uri ng pagpili ng bersyon f, kung saanhinahati nito ang input nito sa isang pinagsunod-sunod at isang hindi nasortadong rehiyon, at paulit-ulit nitong binabawasan ang hindi nasortadong rehiyon sa pamamagitan ng pagkuha ng pinakamalaking elemento at paglipat nito sa pinagsunod-sunod na rehiyon.

Mga hakbang upang ipatupad ang Quicksort (sa pagtaas ng pagkakasunud-sunod):

  1. Bumuo ng isang max na magbunton kasama ang pag-uuri ng array
  2. Sa poin na itot, ang pinakamalaking item ay nakaimbak sa ugat ng magbunton. Palitan ito ng huling item ng bunton at bawasan ang laki ng magbunton ng 1. Panghuli, ibunton ang ugat ng puno
  3. Ulitin ang mga hakbang sa itaas hanggang sa ang laki ng bunton ay mas malaki sa 1

Narito ang pseudocode na kumakatawan sa Heap Sort Algorithm.

Heapsort (a bilang array) para sa (i = n / 2 - 1) upang i> = 0 heapify (a, n, i) para sa i = n-1 hanggang 0 swap (a [0], a [i]) heapify (a, i, 0) magtatapos para sa pagtatapos para sa heapify (a bilang array, n bilang int, i bilang int) pinakamalaking = i // Initialize pinakamalaking bilang root int l eft = 2 * i + 1 // left = 2 * i + 1 int kanan = 2 * i + 2 // kanan = 2 * i + 2 kung (naiwan ang isang [pinakamalaking]) pinakamalaki = kaliwa kung (kanan isang [pinakamalaki]) pinakamalaking = kanan kung (pinakamalaki! = I) magpalitan ( isang [i], Isang [pinakamalaki]) Heapify (a, n, pinakamalaking) end heapify

Bukod sa mga ito, may iba pang mga pag-uuri ng mga algorithm na hindi gaanong kilala tulad ng, Introsort, Counting Sort, atbp. Paglipat sa susunod na hanay ng mga algorithm sa artikulong 'Mga Istraktura ng Data at Mga Algorithm' na ito, tuklasin natin ang mga naghahanap ng mga algorithm.

Paghahanap ng Mga Algorithm sa Java

Ang paghahanap ay isa sa mga pinakakaraniwan at madalas na ginagawa na mga pagkilos sa mga regular na aplikasyon ng negosyo. Ang mga algorithm sa paghahanap ay mga algorithm para sa paghahanap ng isang item na may tinukoy na mga pag-aari kabilang sa isang koleksyon ng mga item. Tuklasin natin ang dalawa sa pinakakaraniwang ginagamit na mga algorithm sa paghahanap.

Linear Search Algorithm sa Java

Ang linear na paghahanap o sunud-sunod na paghahanap ay ang pinakasimpleng algorithm sa paghahanap. Nagsasangkot ito ng sunud-sunod na paghahanap para sa isang elemento sa ibinigay na istraktura ng data hanggang sa ang elemento ay matagpuan o maabot ang dulo ng istraktura. Kung ang elemento ay natagpuan, pagkatapos ang lokasyon ng item ay ibinalik kung hindi man ang algorithm ay nagbabalik ng Null.

Narito ang pseudocode na kumakatawan sa Linear Search sa Java:

pamamaraan linear_search (isang [], halaga) para sa i = 0 hanggang n-1 kung ang isang [i] = halaga pagkatapos ay i-print ang 'Natagpuan' pagbalik i end kung i-print ang 'Hindi natagpuan' na pagtatapos para sa end linear_search

Ito ay isangbrute-force algorithm.Bagaman tiyak na ito ang pinakasimpla, tiyak na hindi ito ang pinaka-karaniwan, dahil sa kawalan ng husay nito. Pagiging kumplikado ng Oras ng paghahanap ng Linear ay O (N) .

Algorithm ng Paghahanap ng Binary sa Java

Ang paghahanap sa binary, kilala rin bilang paghahanap sa logarithmic, ay isang algorithm ng paghahanap na nahahanap ang posisyon ng isang target na halaga sa loob ng isang nakaayos na array. Hinahati nito ang koleksyon ng pag-input sa pantay na kalahati at ang item ay inihambing sa gitnang elemento ng listahan. Kung ang elemento ay natagpuan, nagtatapos ang paghahanap doon. Iba pa, patuloy kaming naghahanap ng elemento sa pamamagitan ng paghahati at pagpili ng naaangkop na pagkahati ng array, batay sa kung ang target na elemento ay mas maliit o mas malaki kaysa sa gitnang elemento.

Narito ang pseudocode na kumakatawan sa Binary Search sa Java:

Pamamaraan binary_search isang pinagsunod-sunod na array n laki ng array x halaga na hinanap sa lowerBound = 1 upperBound = n habang x hindi natagpuan kung upperBound

Natapos ang paghahanap kapag ang upperBound (aming pointer) ay pumasa sa lowerBound (huling elemento), na nagpapahiwatig na hinanap namin ang buong array at ang elemento ay wala.Ito ang pinakakaraniwang ginagamit na mga algorithm sa paghahanap lalo na sa mabilis na oras ng paghahanap. Ang pagiging kumplikado ng oras ng binary na paghahanap ay O (N) na kung saan ay isang minarkahang pagpapabuti sa O (N) pagiging kumplikado ng oras ng Linear Search.

Dinadala tayo nito sa pagtatapos ng artikulong 'Mga Istraktura at Algorithm ng Data sa Java' na artikulong ito. Saklaw ko ang isa sa pinakamahalaga at mahahalagang paksa ng Java.Inaasahan kong malinaw ka sa lahat ng naibahagi sa iyo sa artikulong ito.

Tiyaking nagsasanay ka hangga't maaari at ibalik ang iyong karanasan.

Suriin ang ni Edureka, isang pinagkakatiwalaang kumpanya sa pag-aaral sa online na may isang network na higit sa 250,000 nasiyahan na mga nag-aaral na kumalat sa buong mundo. Narito kami upang matulungan ka sa bawat hakbang sa iyong paglalakbay, para sa pagiging isang bukod sa mga katanungang ito sa panayam sa java, nakakakuha kami ng isang kurikulum na idinisenyo para sa mga mag-aaral at propesyonal na nais na maging isang Java Developer.

May tanong ba sa amin? Mangyaring banggitin ito sa seksyon ng mga komento ng 'Mga Istraktura ng Data at Algorithm sa Java' artikulo at babalikan ka namin sa lalong madaling panahon.