Zlúčiť triedenie poľa - java, polia, algoritmus

ahoj, mám celý rad 9 prvkov

10 , 5 , 2 , 4 , 6 , 1 , 3 , 2 , 6

Musím to triediť pomocou zlúčiť algoritmus triedenia. Moja otázka je, že číslo 6 sa používa dvakrát, ako to ovplyvní triedenie.

odpovede:

Aby sme pochopili, ako by sa to usporiadalo, pozrime sa na to, ako skutočne funguje algoritmus zlučovania.

split each element into partitions of size 1
recursively merge adjancent partitions
for i = leftPartStartIndex to rightPartLastIndex inclusive
if leftPartHeadValue <= rightPartHeadValue
copy leftPartHeadValue
else: copy rightPartHeadValue
copy elements back to original array

Takže umožňuje zobrať dané pole [10 , 5 , 2 , 4 , 6 , 1 , 3 , 2 , 6] Tu je príklad, ako algoritmus skutočne funguje

Spočiatku rozdelte pole na oddiely veľkosti1. Každá hodnota v poli je teda samostatným oddielom. Teraz zlúčte 10 v pozícii 0 a 5 v pozícii 1 do jedného oddielu. Od 10> 5 skopírujte 5 do nového dočasného poľa veľkosti 2, teraz je pravý oddiel prázdny, a preto doň skopírujte 10, takže teraz máte dočasné pole, ktoré je [5,10] Potom ho skopírujte späť do pôvodného poľa na pozíciách, ktoré ho robia

[5,10,2,4,6,1,3,2,6] Teraz zlúčte oddiely [5,10] na [2] v 2. indexe. Od 5> 2 skopírujte 2 do dočasného poľa. Pretože pravý oddiel je prázdna kópia 5 do dočasného poľa napravo a podobná s 10, čím sa vytvorí [2,5,10], Teraz skopírujte položky späť do pôvodného poľa. [2,5,10,4,6,1,3,2,6]

Teraz zlúčte oddiely [4,6] a od 4 <6 skopírujte 4 do ľavého oddielu a 6 do pravého oddielu dočasného poľa a skopírujte ich späť do pôvodného poľa. V tomto prípade je pole nezmenené a stále vyzerá rovnako. [2,5,10,4,6,1,3,2,6].

Teraz zlúčte oddiely [2,5,10] na [4,6], Od 2 <4 skopírujte 2 do dočasného poľa, potom od 4 <5, skopírujte 4 do poľa, potom od 5 <6 kópie 5 a tak ďalej, až kým nebudeme mať novú dočasnú skupinu nových oddielov. [2,4,5,6,10] a potom skopírujte prvky do pôvodného poľa [2,4,5,6,10,1,3,2,6]

Teraz zlúčte položky [1,3] a podobne s [2,6] pretože hodnota na ľavej strane oddielu je nižšia ako hodnota napravo. Potom zlúčiť [1,3] na [2,6], Od 1 <2 skopírujte 1 do dočasného poľa a potom 2 a tak získajte nový oddiel [1,2,3,6] a skopírujte ho späť do pôvodného poľa [2,4,5,6,10,1,2,3,6].

Nakoniec máme dve oddiely na zlúčenie, t. [2,4,5,6,10] a [1,2,3,6], Opakujte podobný postup, pretože 1 <2, kópia 1do dočasného poľa a potom 2 (pretože 2 v ľavom oddiele <= 2 v pravom oddiele), takže hodnota 2 z ľavého oddielu sa skopíruje do dočasného poľa. Potom sa 4 porovná s 2 a hodnota 2 z pravého oddielu sa skopíruje do nového dočasného poľa. Potom sa skopíruje 4> 3, takže 3 sa potom skopíruje 4 <6, potom sa skopíruje 4 a potom 5 <6 (pravý oddiel) skopíruje 5 do dočasného poľa. Keď narazíme na 6 (ľavý oddiel) na 6 (pravý oddiel) a dodržiavame podmienku 6 <= 6 hodnota 6 z ľavého oddielu sa skopírujedo dočasného poľa. Potom sa 6 v pravom oddiele porovná s 10 a 6 <10, takže 6 sa skopíruje do dočasného poľa a potom 10. Potom sa celé dočasné pole skopíruje do pôvodného poľa, čím sa získa konečné pole. [1,2,2,3,4,5,6,6,10]