Įvadas į suliejimo rūšiavimo algoritmą

„Merge sort“ yra rūšiavimo algoritmas, pagrįstas „padalink ir užkariauk“ technika. Tai vienas efektyviausių rūšiavimo algoritmų.

Šiame straipsnyje sužinosite apie sujungimo rūšiavimo algoritmo veikimą, sujungimo rūšiavimo algoritmą, jo laiko ir erdvės sudėtingumas ir jo įgyvendinimas įvairiomis programavimo kalbomis, tokiomis kaip C ++, Python ir „JavaScript“.

Kaip veikia suliejimo rūšiavimo algoritmas?

„Merge sort“ veikia padalijimo ir užkariavimo principu. „Merge sort“ masyvą pakartotinai suskirsto į du vienodus poskyrius, kol kiekvienas poskyris susideda iš vieno elemento. Galiausiai visi šie poskyriai sujungiami taip, kad gautas masyvas būtų surūšiuotas.

Šią sąvoką galima efektyviau paaiškinti pavyzdžiu. Apsvarstykite nerūšiuotą masyvą su šiais elementais: {16, 12, 15, 13, 19, 17, 11, 18}.

Čia sujungimo rūšiavimo algoritmas masyvą padalija į dvi puses, pats save vadina dviem pusėmis ir sujungia dvi surūšiuotas puses.

Sujungti rūšiavimo algoritmą

Žemiau yra sujungimo rūšiavimo algoritmas:

„MergeSort“ (arr [], leftIndex, rightIndex)
jei leftIndex> = rightIndex
grįžti
Kitas
Raskite vidurinį indeksą, kuris masyvą padalija į dvi puses: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Pirmos pusės kvietimas „MergeSort ()“: 
Skambučių sujungimo rūšiavimas (arr, leftIndex, middleIndex)
Skambinkite „mergeSort“) antrai pusei:
Skambučių sujungimo rūšiavimas (arr, middleIndex + 1, rightIndex)
Sujunkite dvi 2 ir 3 žingsniuose surūšiuotas puses:
Skambučių sujungimas (arr, leftIndex, middleIndex, rightIndex)

Susijęs: Kas yra rekursija ir kaip ją naudojate?

Sujungimo rūšiavimo algoritmo laiko ir erdvės sudėtingumas

Sujungimo rūšiavimo algoritmą galima išreikšti tokiu pasikartojimo ryšiu:

T (n) = 2T (n / 2) + O (n)

Išsprendę šį pasikartojimo santykį naudodami pagrindinės teoremos ar pasikartojimo medžio metodą, jūs gausite sprendimą kaip O (n logn). Taigi sujungimo rūšiavimo algoritmo laiko sudėtingumas yra O (n prisijungti).

Geriausias sujungimo rūšies laiko sudėtingumas: O (n prisijungti)

Vidutinis sujungimo rūšies laiko sudėtingumas: O (n prisijungti)

Blogiausias atvejo sudėtingumo laikas: O (n prisijungti)

Susijęs: Kas yra „Big-O“ žymėjimas?

Pagalbinės erdvės sudėtingumas suliejimo rūšiavimo algoritmo yra O (n) kaip n pagalbinė erdvė reikalinga įgyvendinant sujungimo rūšiavimą.

C ++ suliejimo rūšiavimo algoritmo įgyvendinimas

Žemiau yra sujungimo rūšiavimo algoritmo C ++ įgyvendinimas:

// C ++ diegimas
// sujungti rūšiavimo algoritmą
# įtraukti 
naudojant vardų sritį std;
// Ši funkcija sujungia du arr [[] poaibius
// Kairysis poskyris: arr [leftIndex..middleIndex]
// Dešinysis požemis: arr [middleIndex + 1..rightIndex]
negaliojantis sujungimas (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Sukurkite laikinus masyvus
int L [leftSubarraySize], R [rightSubarraySize];
// Duomenų kopijavimas į laikinas masyvas L [] ir R []
už (int i = 0; i L [i] = arr [kairysisIndex + i];
už (int j = 0; j R [j] = arr [vidurinis rodiklis + 1 + j];
// Sujungti laikinus masyvus atgal į arr [leftIndex..rightIndex]
// Kairiojo poskyrio pradinis indeksas
int i = 0;
// Pradinis dešiniojo poskyrio rodiklis
int j = 0;
// Pradinis sujungto subarterio indeksas
int k = leftIndex;
while (i {
jei (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
Kitas
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Jei L yra keletas likusių elementų []
// Kopijuoti į arr []
o (i {
arr [k] = L [i];
i ++;
k ++;
}
// Jei R yra keletas likusių elementų
// Kopijuoti į arr []
o (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
jei (leftIndex> = rightIndex)
{
grįžti;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
sujungti (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcija spausdinti elementus
masyvo //
void printArray (int arr [], int dydis)
{
už (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Vairuotojo kodas
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int dydis = sizeof (arr) / sizeof (arr [0]);
cout << "Nesurūšiuotas masyvas:" << endl;
printArray (arr, dydis);
sulietiSort (arr, 0, dydis - 1);
cout << "Rūšiuotas masyvas:" << endl;
printArray (arr, dydis);
grąžinti 0;
}

Išvestis:

Nerūšiuotas masyvas:
16 12 15 13 19 17 11 18 
Rūšiuotas masyvas:
11 12 13 15 16 17 18 19

„JavaScript“ sujungimo rūšiavimo algoritmo įgyvendinimas

Žemiau yra sujungimo rūšiavimo algoritmo „JavaScript“ diegimas:

// „JavaScript“ diegimas
// sujungti rūšiavimo algoritmą
// Ši funkcija sujungia du arr [[] poaibius
// Kairysis poskyris: arr [leftIndex..middleIndex]
// Dešinysis požemis: arr [middleIndex + 1..rightIndex]
funkcija sujungti (arr, leftIndex, middleIndex, rightIndex) {
tegul leftSubarraySize = middleIndex - leftIndex + 1;
tegul rightSubarraySize = rightIndex - middleIndex;
// Sukurkite laikinus masyvus
var L = naujas masyvas (leftSubarraySize);
var R = naujas masyvas (rightSubarraySize);
// Duomenų kopijavimas į laikinas masyvas L [] ir R []
už (tegul i = 0; iL [i] = arr [kairysisIndex + i];
}
už (tegul j = 0; jR [j] = arr [vidurinis rodiklis + 1 + j];
}
// Sujungti laikinus masyvus atgal į arr [leftIndex..rightIndex]
// Kairiojo poskyrio pradinis indeksas
var i = 0;
// Pradinis dešiniojo poskyrio rodiklis
var j = 0;
// Pradinis sujungto subarterio indeksas
var k = leftIndex;
while (i {
jei (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
Kitas
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Jei L yra keletas likusių elementų []
// Kopijuoti į arr []
o (i {
arr [k] = L [i];
i ++;
k ++;
}
// Jei R yra keletas likusių elementų
// Kopijuoti į arr []
o (j {
arr [k] = R [j];
j ++;
k ++;
}
}
funkcija mergeSort (arr, leftIndex, rightIndex) {
jei (leftIndex> = rightIndex) {
grįžti
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
sujungti (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcija spausdinti elementus
masyvo //
funkcija printArray (arr, dydis) {
už (tegul i = 0; idocument.write (arr [i] + "");
}
document.write ("
");
}
// Vairuotojo kodas:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var dydis = arr.length;
document.write ("Nesurūšiuotas masyvas:
");
printArray (arr, dydis);
sulietiSort (arr, 0, dydis - 1);
document.write ("Rūšiuotas masyvas:
");
printArray (arr, dydis);

Išvestis:

Nerūšiuotas masyvas:
16 12 15 13 19 17 11 18
Rūšiuotas masyvas:
11 12 13 15 16 17 18 19

Susijęs: Dinaminis programavimas: pavyzdžiai, bendros problemos ir sprendimai

„Python“ sujungimo rūšiavimo algoritmo įgyvendinimas

Žemiau yra sujungimo rūšiavimo algoritmo „Python“ diegimas:

# Python diegimas
# sujungti rūšiavimo algoritmą
def sulietiSort (arr):
jei len (arr)> 1:
# Vidutinio masyvo indekso radimas
middleIndex = len (arr) // 2
# Kairė masyvo pusė
L = arr [: middleIndex]
# Dešinė masyvo pusė
R = arr [vidurinis rodiklis:]
# Rūšiavimas pirmoje masyvo pusėje
sujungtiSort (L)
# Antros masyvo pusės rūšiavimas
sujungtiSort (R)
# Pradinis kairiojo poskyrio indeksas
i = 0
# Pradinis dešiniojo subarterio indeksas
j = 0
# Pradinis sujungto subarterio indeksas
k = 0
# Kopijuoti duomenis į tempimo masyvus L [] ir R []
o i jei L [i] arr [k] = L [i]
i = i + 1
Kitas:
arr [k] = R [j]
j = j + 1
k = k + 1
# Tikrinimas, ar yra likusių elementų
o aš arr [k] = L [i]
i = i + 1
k = k + 1
o j arr [k] = R [j]
j = j + 1
k = k + 1
# Funkcija spausdinti elementus
# masyvo
def printArray (arr, dydis):
i diapazone (dydis):
spausdinti (arr [i], pabaiga = "")
spausdinti ()
# Vairuotojo kodas
arr = [16, 12, 15, 13, 19, 17, 11, 18]
dydis = len (arr)
spausdinti ("Nerūšiuotas masyvas:")
spausdinti masyvą (arr, dydis)
sujungtiSort (arr)
spausdinti ("Rūšiuotas masyvas:")
spausdinti masyvą (arr, dydis)

Išvestis:

Nerūšiuotas masyvas:
16 12 15 13 19 17 11 18
Rūšiuotas masyvas:
11 12 13 15 16 17 18 19

Suprasti kitus rūšiavimo algoritmus

Rūšiavimas yra vienas iš dažniausiai naudojamų algoritmų programuojant. Galite rūšiuoti elementus įvairiomis programavimo kalbomis naudodami įvairius rūšiavimo algoritmus, pvz., Greitasis, burbulinis, sujungimo rūšiavimas, įterpimo rūšiavimas ir kt.

Burbulo rūšiavimas yra geriausias pasirinkimas, jei norite sužinoti apie paprasčiausią rūšiavimo algoritmą.

Įvadas į burbulų rūšiavimo algoritmą

„Bubble Sort“ algoritmas: puikus įvadas į masyvų rūšiavimą.

Skaitykite toliau

Apie autorių