Apakah algoritma pengisihan yang stabil?

Algoritma pengisihan yang stabil termasuk: 1. Isih buih 3. Isih sisipan; Isih timbunan.

Persekitaran pengendalian tutorial ini: sistem Windows 10, komputer Dell G3.

Analisis kestabilan algoritma pengisihan biasa dan berikan sebab mudah untuk setiap algoritma.

Algoritma pengisihan stabil:

1 pengisihan adalah untuk menggerakkan elemen kecil ke hadapan atau menggerakkan elemen besar ke belakang. Perbandingan ialah perbandingan dua elemen yang bersebelahan, dan pertukaran juga berlaku antara kedua-dua elemen ini. Jadi, jika dua elemen adalah sama, saya tidak fikir anda akan menukarnya dengan membosankan.

Jika dua elemen yang sama tidak bersebelahan, maka walaupun kedua-duanya bersebelahan melalui pertukaran pasangan sebelumnya, mereka tidak akan ditukar pada masa ini, jadi susunan elemen yang sama tidak berubah, jadi terdapat jenis Bubble risiko ialah algoritma pengisihan yang stabil.

2. Pengisihan pilihan

Isih pilihan memilih elemen semasa terkecil untuk setiap kedudukan, contohnya, memilih yang terkecil untuk kedudukan pertama dan menetapkan elemen terkecil kepada Elemen yang tinggal Pilih elemen kedua terkecil untuk elemen kedua, dan seterusnya, sehingga elemen ke tidak perlu dipilih, kerana ia adalah satu-satunya elemen terbesar yang tinggal. Kemudian, dalam pemilihan, jika elemen semasa adalah lebih kecil daripada elemen, dan elemen kecil muncul selepas elemen yang sama dengan elemen semasa, maka kestabilan akan dimusnahkan selepas pertukaran.

agak sukar untuk disebut Sebagai contoh, dalam urutan n-1, kita tahu bahawa memilih

elemen ke

dalam hantaran pertama akan ditukar dengan 5 8 5 2 9, kemudian ada. akan menjadi 1 dimusnahkan, jadi isihan pemilihan bukan algoritma pengisihan yang stabil. 5223. Isih sisipan 5

Isih sisipan memasukkan satu elemen pada satu masa berdasarkan urutan kecil yang telah dipesan. Sudah tentu, pada mulanya, urutan tertib kecil ini hanya mempunyai satu elemen, iaitu elemen pertama. Perbandingan bermula dari penghujung urutan tertib, iaitu elemen yang ingin anda masukkan dibandingkan dengan yang terbesar yang telah disusun Jika lebih besar daripadanya, masukkan terus di belakangnya, jika tidak, teruskan melihat ke hadapan sehingga anda cari elemen yang sepatutnya dimasukkan ke dalamnya. Jika ia menjumpai elemen yang sama dengan elemen yang disisipkan, maka elemen yang disisipkan meletakkan elemen yang akan disisipkan selepas elemen yang sama.

Oleh itu, susunan unsur yang sama tidak berubah.

4. Isih cepat

Isih cepat mempunyai dua arah. > ialah pusat Subskrip tatasusunan unsur biasanya diambil sebagai elemen tatasusunan. Subskrip di sebelah kanan pergi ke kiri, apabila

.

a[i] <= a[center_index]Jika i atau j tidak boleh berjalan, center_index, tukarkan 0 dan j, dan ulangi proses di atas sehingga a[j]>a[center_index]. Tukar

dan

untuk melengkapkan isihan pantas. Apabila elemen pusat dan i<=j ditukar, ia berkemungkinan besar akan mengganggu kestabilan elemen sebelumnya Sebagai contoh, urutannya ialah a[i], dan kini elemen pusat a[j] dan i>j (a[j]. elemen ke, seterusnya Pertukaran (bernombor bermula dari a[center_index]) akan mengganggu kestabilan elemen 3, jadi isihan pantas ialah algoritma pengisihan yang tidak stabil Ketidakstabilan berlaku pada masa apabila elemen pusat dan a[j] ditukar. a[j]5 3 3 4 3 8 9 10 1155. Isih Gabung 351Isih Gabung secara rekursif membahagikan jujukan kepada jujukan pendek ialah jujukan pendek hanya mempunyai elemen

(dianggap sebagai dipesan terus) Atau

jujukan ( perbandingan dan pertukaran), dan kemudian gabungkan setiap jujukan segmen tersusun ke dalam urutan panjang tertib, dan teruskan bergabung sehingga jujukan asal semuanya diisih. Ia boleh didapati bahawa apabila terdapat atau

elemen,

elemen tidak akan ditukar Jika 1 elemen sama saiz, tiada siapa yang akan menukarnya dengan sengaja, yang tidak akan memusnahkan kestabilan. 21Jadi, dalam proses penggabungan urutan tertib pendek, adakah kestabilan itu musnah? 12Tidak, semasa proses penggabungan kami boleh memastikan bahawa jika kedua-dua elemen semasa adalah sama, kami akan menyimpan elemen urutan sebelumnya di hadapan jujukan hasil, sekali gus memastikan kestabilan. Oleh itu, pengisihan gabungan juga merupakan algoritma pengisihan yang stabil. 12

6. Isih Radix

Isih radix adalah untuk mengisih mengikut tertib rendah dahulu, dan kemudian mengumpulkan >

Dan seterusnya, sehingga kedudukan tertinggi. Kadang-kadang sesetengah atribut mempunyai susunan keutamaan Mereka diisih mengikut keutamaan rendah dahulu, kemudian mengikut keutamaan tinggi Urutan terakhir ialah mereka yang mempunyai keutamaan tinggi didahulukan, dan yang mempunyai keutamaan tinggi dan keutamaan yang sama didahulukan. Isihan Radix adalah berdasarkan isihan berasingan dan koleksi berasingan, jadi ia adalah algoritma isihan yang stabil.

7. Pengisihan bukit (cangkang)

Isihan bukit ialah penyisipan unsur mengikut panjang penyegerakan yang berbeza Apabila elemen sangat tidak teratur pada permulaannya saiz langkah adalah yang terbesar, jadi bilangan elemen dalam isihan sisipan adalah kecil dan kelajuannya sangat pantas.

Apabila elemen pada asasnya disusun dan saiz langkahnya kecil, isihan sisipan adalah sangat cekap untuk urutan tertib. Oleh itu, kerumitan masa pengisihan Bukit akan lebih baik daripada O(n^2). Disebabkan oleh pelbagai pengisihan sisipan, kita tahu bahawa satu pengisihan sisipan adalah stabil dan tidak akan mengubah susunan relatif unsur yang sama Walau bagaimanapun, dalam proses pengisihan sisipan yang berbeza, unsur yang sama mungkin bergerak dalam pengisihan sisipan masing-masing, dan akhirnya kestabilan mereka akan. perubahan.

8. Isih timbunan

Kita tahu bahawa struktur timbunan ialah anak-anak nod i ialah nod 2 * i dan 2 * i 1, dan timbunan atas besar memerlukan nod induk Lebih besar daripada atau sama dengan nod anak 2nya, timbunan atas kecil memerlukan nod induk kurang daripada atau sama dengan nod anak 2nya. Dalam urutan dengan panjang n, proses pengisihan timbunan adalah untuk memilih yang terbesar (timbunan atas besar) atau yang terkecil (timbunan atas kecil) bermula dari n / 2th dan nod anaknya dengan jumlah 3 nilai ini 3 Pilihan antara elemen pastinya tidak memusnahkan kestabilan. Tetapi apabila memilih elemen untuk nod induk n / 2-1, n/2-2, ...1, kestabilan akan musnah. Ada kemungkinan bahawa n/2nod induk ke menukar elemen berikut, tetapi n/2-1nod induk ke tidak menukar elemen yang serupa berikut, maka kestabilan antara dua elemen yang sama dimusnahkan. Oleh itu, isihan timbunan bukanlah algoritma pengisihan yang stabil.

Untuk lebih banyak pengetahuan berkaitan, sila lawati ruangan Soalan Lazim!

Atas ialah kandungan terperinci Apakah algoritma pengisihan yang stabil?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!