Az adatok rendezése
A rendelési statisztikák kiszámításának feladata az n elemek sorrendjében megtalálni a k-es legkisebb elemet. Ezt a problémát néha a k. Sorrendi statisztikák megtalálásának problémájaként nevezik meg. Amikor k = 1, akkor a probléma csökkenti a szekvencia legkisebb elemének megállapítását, és k = n a legnagyobb elemet, és nem több, mint O (n) lépés. Az ordinális statisztikák kiszámításának egyik problémája az alábbi: rendezzük el az eredeti szekvenciát a nem csökkenő elemek sorrendjében, és vegyük be a k-es elemet. Ugyanakkor azonban figyelembe kell venni a valódi probléma követelményeit, amelyek érdekeit figyelembe véve a rendelési statisztikákat kiszámítják.
Először is, kiderül, hogy egy sorrendben a több elem kulcsai (k-d, (k + 1) -d) ... ugyanazt jelentik. Aztán meg kell vizsgálni, hogy ezek az elemek ugyanolyan sorrendben kövessék egymást, mint az eredeti sorrendben, vagy nem szükséges. Az első esetben a kezdeti szekvencia sorrendjét a stabil szortírozás egyik módszerével kell végrehajtani, a második esetben mindenféle szortírozási módszer használható.
Második. Van egy vagy több rendelési statisztika? Ettől függően előnyös lehet algoritmust alkalmazni.
Harmadik. az algoritmus kiválasztását az eredeti szekvencia n elemeinek száma befolyásolja.
Végül, ha az eredeti sorrendben kell tartani anélkül, hogy a változás, hogy megtalálják rendstatisztikák létre kell hozni egy másolatot az eredeti sorozat, vagy egy sor kulcsfontosságú eleme az eredeti sorrendet. Kulccsal tömb előnyös lehet abban az esetben, ahol az elemek az eredeti szekvencia egy komplex struktúra és azok változásait a folyamat a számítástechnikai szekvencia struktúrák igényel jelentős időt. Ha a kereslet stabil szortírozás nem szükséges, de lehetséges, hogy egy rekurzív eljárás alapján Hoare quicksort (Quicksort), amely a leggyorsabb átlagos sorrendje.
Ellentétben a rekurzív eljárásban a megállapítás a k-adik érdekében statisztika a gyors rendezési eljárások Hoare az, hogy először is, miután a két csoportra osztották, hogy csoport van kiválasztva ko¬toroy egy második elem, és, másodszor, hogy Továbbá csak ezt a csoportot dolgozzák fel, és nem mindkét csoportot, ahogy a Hoare gyors sorrendjében történik.
Az eltöltött idő megtalálni a k-adik érdekében statisztikai módszerrel, mint az egyik és a másik, függ a sikeres kiválasztása a referencia elem csoportokba való osztás. Az idő minimális, ha minden egyes lépésnél a csoportok körülbelül ugyanannyi elemet tartalmaznak. Bebizonyosodott, hogy ha minden menetben végrehajtásra kerül akár még a forgatáson alkotó előző 9/10, a végrehajtási idő a megrendelés O (n), és a legrosszabb esetben - nem több, mint O (n 2). Lineáris módszer a rendes statisztikák megtalálásához, a legrosszabb esetben biztosítja az O (n) sorrend végrehajtását. Ez a módszer egy "jó" támogató elem keresésén alapul, és számos elemhez tartozó szekvenciákhoz használatos.