Quicksort rite te tikanga hōtaka

I roto i te 1960, whakawhanakehia K. A. Hoar he tikanga mo te kōmaka tere o ngā mōhiohio, ka te rongonui tino. Kei te whānui teie mahana whakamahia te reira i roto i te hōtaka, kia rite te mea he rota o ngā āhuatanga pai: Ka taea te whakamahi i te reira no te take whānui, e titau te reira i te hua iti i roto i te mahara atu, hototahi ki ngā momo rerekē o te rārangi, me te ngāwari ki te whakatinana. Ko reira he drawbacks, e kua Quicksort: te whakamahi i mahi whakaaetia he rota o hape, a ko reira ahua iu.

Heoi, ko reira te putanga tino ako. I muri i te Hoare utu tuatahi, he tokomaha mahi tona ako mātotoru. whakapumautia turanga nui i runga i ngā pātai ariā o te imiraa i te wa i pau i runga i te mahi, e pou nei i te taunakitanga tëtehi. He nga tono tino ki te whakapai ake i te hātepe taketake, me te nui haere tere.

Ko te tino noa Quicksort, e taea te kitea i te reira mau vahi atoa. I tona pūtake whakatinana te tikanga ko TList.Sort, reira i roto i putanga katoa (anake 1) Delphi, te mahi whare pukapuka o te wā ka mau te reira ki te whakaoti, qsort i C ++.

Ka taea te whakatakoto i te parau tumu taketake o te mahi kia rite ki te "wehenga me te wikitoria". e tupu whawhati te reira i te rārangi ki e rua ngā rōpū, me te e kōmaka mo ia wahi i tahaki. whai te reira e kia utua atu te aro ki te tukanga wehenga, i roto i nei puta te whai ake: kua whakaritea e te huānga turanga, me te kua ngā anō tona rārangi katoa. Hanga ki te maui o te rōpū o ngā kaitono, te uara o te mea iti iho i te tahi atu ture katoa whakawhiti. Huri i te reira i roto i taua i te huānga matua i roto i te rārangi kōmaka kei roto i tona wahi tika. Ko te atamira i muri - he wero mahi kōmaka recursive mō ngā taha e rua o nga āhuatanga whanaunga ki te turanga. mutu te reira i te tukanga mahi anake, ki te kei te rārangi kotahi anake huānga, e ko te ki kia kōmaka. Ko te kupu, i roto i te tikanga ki te rangatira i te mahi hōtaka rite te ahua tere, he mea e tika ana ki te mohio te mahi o hātepe taumata-raro: he) te whiriwhiri o te mema turanga; b) ki te rārangi o te raupapa whai hua tino hua e rua ngā huinga ki ngā uara iti me te nui.

A haamatau ki te mau parau tumu matamua. A, no te kōwhiri i te mema turanga, i pā atu kia tīpakohia i te rārangi o toharite. Na i runga i te mea kiano i matao te wehea ki e rua ngā haurua rite. tātai Just te uara toharite ko te tino uaua i roto i te rārangi, ka pena bypasses ara te kōmaka tere tenei taha tuanaki. Ko te kōwhiringa o te huānga taketake ki te uara mōrahi mōkito ranei - kahore ano te kōwhiringa pai. I roto i te take hanga taua faaotiraa o tetahi ka whai rārangi kau, me te rua o nga ki tonu i. No reira te mutunga e rite te mema turanga kia kotahi e te mea ofi ki te toharite i whiriwhiri, engari ki runga ki te mōrahi me te mōkito.

Kia takoto te kōwhiringa e, ka taea e koe te haere tonu ki te hātepe whāwehe. Tenei-ka karanga kia koropiko roto ahua tere. hanga nga mea katoa i runga i rua taupū Access tere: haere tuatahi i runga i te huānga i mahue ki matau, te tuarua, i runga i te anga ke, i matau ki te mahue. E haamata te tika mahi mahia: ko te taupū runga i te rārangi, me te whakarite i nga uara katoa ki te matua. He oti te huringa ina he iti iho i te rite ranei ki te kaupapa te huānga. Ko, i reira te mea he whakarite me te heke te uara o te taupū. I runga i te ringa maui, ka oti te mahi e nui atu i uara rite ranei. Here, te piki uara whakarite.

I tenei wā o te wawahi hātepe papatono e Kei roto quicksort, kia ara ake e rua ngā āhuatanga. Ko te tuatahi Ko e te taupū i runga i te maui, ko te iti iho i te tika. tohu he hapa tenei, ka i reira he āhuatanga i runga i nei i kī ai i roto i te rārangi kei roto i te raupapa he. Huaputa - taui i to ratou wahi. Ko te āhuatanga tuarua ko ina he rite ki whiti ranei e rua o te tīwae. tohu tenei he wehenga angitu o te rārangi, e ko, he oti nei te mahi.