Kaip įdiegti „QuickSort“ „Java“?

Šis straipsnis supažindins su kitu „Skirstymo ir užkariavimo“ rūšiavimo algoritmu, kuris yra „QuickSort In Java“, ir tęsite jį demonstruodami.

„QuickSort“ yra padalijimo ir užkariavimo algoritmas. Skirstymo ir užkariavimo algoritmo projektavimo paradigmoje problemas rekursyviai padalijame į subproblemas, tada išsprendžiame subproblemas ir pagaliau sujungiame sprendimus, kad rastume galutinį rezultatą. Šiame straipsnyje mes sutelksime dėmesį į „QuickSort In“

Tolimesni patarimai bus aptarti šiame straipsnyje,



Pradėkime!

Vieną dalyką, kurį reikia nepamiršti skirstant problemas į subproblemas, yra tai, kad subproblemų struktūra nesikeičia nuo pradinės problemos.
Skirstymo ir užkariavimo algoritme yra 3 veiksmai:



  • Skirstykite: išskaidykite problemą į subproblemas
  • Užkariaukite: rekursyviai spręsdami papunkčius
  • Sujungti: derinant sprendimus gaunamas galutinis rezultatas

Vaizdas - greitas rūšiavimas „Java“ - „Edureka“

Yra įvairių algidmų, paremtų skaldyk ir užvaldyk paradigma. Tarp jų yra greitas rūšiavimas ir sujungimo rūšiavimas.

Nors blogiausias „QuickSort“ laiko sudėtingumas yra O (n2), kuris yra daugiau nei daugelio kitų rūšiavimo algoritmų, tokių kaip „Merge Sort“ ir „Heap Sort“, „QuickSort“ praktiškai yra greitesnis, nes jo vidinę kilpą galima efektyviai įgyvendinti daugumoje architektūrų realaus pasaulio duomenys.



Pakalbėkime apie greito rūšiavimo algoritmo įgyvendinimą. „Quicksort“ algoritmai paima „pivot“ elementą ir padalija masyvą aplink „pivot“ elementą. Yra keletas „Quicksot“ variantų, kurie priklauso nuo to, kaip pasirenkate sukimo elementą. Yra keli būdai pasirinkti šarnyrinį elementą:

  • Pirmo elemento pasirinkimas
  • Pasirinkite paskutinį elementą
  • Atsitiktinio elemento pasirinkimas
  • Vidutinio elemento parinkimas

Kitas svarbus dalykas, kurį reikia suprasti, yra „Partition (“) funkcija greito rūšiavimo algoritme. Pasiskirstymo funkcija, skirta paimti pasukamą elementą, pastatyti jį į reikiamą padėtį, visus mažesnius nei sukamasis elementas elementus perkelia į kairę, o visus elementus - į dešinę. „Quicksort“ tam reikia laiko.
Tada masyvas yra padalintas į dvi dalis iš „pivot“ elemento (t. Y. Elementų, mažesnių nei „pivot“, ir elementų, didesnių nei „pivot“) ir abu masyvai yra rekursyviai rūšiuojami naudojant „Quicksort“ algoritmą.

skambinkite pagal nuorodą c ++ pavyzdys

Dabar, kai suprantame „QuickSort“ algoritmo veikimą. Supraskime, kaip įdiegti „Quicksort“ algoritmą „Java“.

„QuickSort“ Funkcija:

/ * „Quicksort“ funkcijai reikia, kad masyvas būtų rūšiuojamas pagal mažiausią ir didžiausią indeksą * /

negaliojantis rūšiavimas (int arr [], int lowIndex, int highIndex) {// Iki lowIndex = highIndex if (lowIndex

Dabar pažvelkime į skaidymo kodą, kad suprastume, kaip jis veikia.

Padalijimas Kodas

Skirstymo kode mes pasirinksime paskutinį elementą kaip sukimo elementą. Mes kertame visą masyvą (t. Y. Mūsų atveju naudojame kintamąjį j). Mes sekame paskutinį mažiausią masyvo elementą (t. Y. Mūsų atveju naudojame kintamąjį i). Jei randame bet kurį elementą, mažesnį už pasukimą, judame dabartinį elementą a [j] su arr [i], kitaip mes einame toliau.

int skaidinys (int arr [], int lowIndex, int highIndex) {// Paskutinio elemento sudarymas kaip pasukimas int pivot = arr [highIndex] // Naudojant i sekti smulkesnius elementus nuo pasukimo int i = (lowIndex-1) už (int j = lowIndex j

Dabar, kai supratote „Quicksort“ ir skaidinio funkciją, leiskite mums greitai pažvelgti į visą kodą

pagrindinė „Java“ programos struktūra

„QuickSort“ „Java“ kodas

klasės „QuickSort“ {// skaidinio metodas int skaidinys (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1), skirtas (int j = lowIndex j

// Rūšiavimo metodas

void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex

// Masyvo spausdinimo metodas

static void printArray (int arr []) {int n = arr.length for (int i = 0 i

// Pagrindinis metodas

public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('rūšiuojamas masyvas') printArray (arr)}}

Išvestis:

Rezultatas - greitas rūšiavimas „Java“ - „Edureka“

Dabar, atlikę minėtą „Java“ programą, būtumėte supratę, kaip veikia „QuickSort“ ir kaip ją įdiegti „Java“.Taigi mes priėjome šį straipsnį apie „Quicksort in Java“. Jei norite sužinoti daugiau,patikrinkite sukūrė patikima internetinė mokymosi įmonė „Edureka“. „Edureka“ „Java J2EE“ ir SOA mokymo ir sertifikavimo kursai yra skirti mokyti jus tiek pagrindinėms, tiek pažangesnėms „Java“ koncepcijoms kartu su įvairiomis „Java“ sistemomis, tokiomis kaip „Hibernate & Spring“.

Turite mums klausimą? Prašau tai paminėti šio tinklaraščio komentarų skiltyje ir mes kuo greičiau susisieksime su jumis.