Qhov txawv ntawm Npuas Sort thiab Xaiv Xaiv

Qhov txawv ntawm Npuas Sort thiab Xaiv Xaiv
Qhov txawv ntawm Npuas Sort thiab Xaiv Xaiv

Video: Qhov txawv ntawm Npuas Sort thiab Xaiv Xaiv

Video: Qhov txawv ntawm Npuas Sort thiab Xaiv Xaiv
Video: Qhov Txawv Ntawm Lus Hmoob Thiab Lus Mab Mawb 2024, Hlis ntuj nqeg
Anonim

Npuas Ntaus vs Xaiv Xaiv

Npuas txheeb yog qhov kev txheeb xyuas cov txheej txheem uas ua haujlwm los ntawm kev mus dhau cov npe kom raug txheeb xyuas dua thaum sib piv cov khub ntawm cov khoom uas nyob ib sab. Yog hais tias ib khub ntawm cov ntsiab lus nyob rau hauv qhov kev txiav txim tsis ncaj ncees lawm lawv tau swapped los tso rau hauv qhov kev txiav txim kom raug. Qhov kev hla no rov ua dua kom txog thaum tsis muaj kev sib pauv ntxiv lawm. Kev xaiv xaiv kuj yog ib qho kev txheeb xyuas algorithm, uas pib los ntawm kev nrhiav qhov tsawg kawg nkaus hauv daim ntawv teev npe thiab sib pauv nrog thawj lub caij. Cov txheej txheem no rov ua dua rau cov seem ntawm cov npe los ntawm kev muab cov khoom sib pauv hauv kev txiav txim.

Dab tsi yog Bubble Sort?

Npuas txheeb yog qhov kev txheeb xyuas cov txheej txheem uas ua haujlwm los ntawm kev mus dhau cov npe kom raug txheeb xyuas dua thaum sib piv cov khub ntawm cov khoom uas nyob ib sab. Yog hais tias ib khub ntawm cov ntsiab lus nyob rau hauv qhov kev txiav txim tsis ncaj ncees lawm lawv tau swapped los tso rau hauv qhov kev txiav txim kom raug. Qhov kev sib tw no rov ua dua kom txog thaum tsis tas yuav muaj kev sib pauv ntxiv (uas txhais tau tias cov npe tau txheeb). Txij li thaum cov khoom me me hauv cov npe tuaj rau saum toj li cov npuas tuaj rau saum npoo, nws tau muab lub npe ua npuas. Bubble sort yog ib qho yooj yim sorting algorithm tab sis nws muaj qhov teeb meem nruab nrab lub sij hawm nyuaj ntawm O (n2) thaum txheeb cov npe nrog n ntsiab. Vim li no, kev sib cais npuas tsis haum rau kev txheeb cov npe nrog ntau cov ntsiab lus. Tab sis vim nws txoj kev yooj yim, kev ua npuas yog qhia thaum qhia txog algorithms.

Kev xaiv xaiv yog dab tsi?

Kev xaiv xaiv kuj yog lwm qhov kev txheeb xyuas cov txheej txheem uas pib los ntawm kev nrhiav qhov tsawg kawg nkaus hauv cov npe thiab sib pauv nrog thawj lub caij. Tom qab ntawd qhov tsawg kawg nkaus yog pom los ntawm cov seem ntawm cov npe (los ntawm lub caij thib ob mus txog rau lub caij kawg hauv daim ntawv teev npe) thiab sib pauv nrog lub caij thib ob. Cov txheej txheem no rov ua dua rau cov seem ntawm cov npe los ntawm kev muab cov khoom sib hloov hauv kev txiav txim. Yog li hauv kev xaiv xaiv, ntawm txhua kauj ruam ntawm cov algorithm, cov npe tau muab faib ua ob ntu uas ib feem muaj cov ntsiab lus txheeb thiab lwm qhov muaj cov ntsiab lus tsis raug. Raws li cov algorithm pib, cov npe txheeb tau loj hlob ntawm sab laug mus rau sab xis. Kev xaiv xaiv kuj muaj qhov nruab nrab lub sijhawm nyuaj ntawm O (n2). Yog li nws kuj tsis haum rau kev txheeb cov npe loj.

Dab tsi yog qhov txawv ntawm Bubble Sort thiab Xaiv Xaiv?

Txawm hais tias ob qho tib si npuas thiab xaiv cov algorithms muaj qhov nruab nrab ntawm cov sij hawm nyuaj ntawm O(n2), cov npuas sib txawv yuav luag txhua lub sijhawm ua tiav los ntawm kev xaiv xaiv. Qhov no yog vim muaj pes tsawg tus swaps xav tau los ntawm ob lub algorithms (npuas xaiv xav tau ntau swaps). Tab sis vim yog qhov yooj yim ntawm kev ua npuas, nws cov lej loj me me heev. Stability yog lwm qhov sib txawv ntawm ob lub algorithms no. Ib tug ruaj khov sorting algorithm, yog ib tug sorting algorithm uas khaws cov kev txiav txim ntawm cov ntaub ntawv yog hais tias daim ntawv teev muaj cov ntsiab lus nrog tus nqi sib npaug. Nyob rau hauv tas li ntawd, kev xaiv xaiv tsis yog ib tug ruaj khov algorithm whereas npuas sort yog ib tug ruaj khov algorithm.

Pom zoo: