Apakah kaedah pengisihan?

Kaedah pengisihan termasuk isihan gelembung, isihan pemilihan, isihan sisipan, isihan cepat, isihan gabung, isihan timbunan, isihan mengira dan isihan baldi. Pengenalan terperinci: 1. Pengisihan buih ialah algoritma pengisihan yang mudah berulang kali merentasi tatasusunan yang hendak diisih, membandingkan dua elemen pada satu masa, dan menukarnya jika susunan itu salah lebih banyak elemen. Jika pertukaran diperlukan sekali lagi, ini bermakna urutan telah diisih 2. Isih pilihan ialah algoritma pengisihan yang mudah dan intuitif. Prinsip kerjanya ialah memilih elemen terkecil daripada elemen data untuk diisih setiap kali, dan seterusnya.

Kaedah pengisihan adalah salah satu algoritma asas yang sering kita perlu gunakan dalam pengaturcaraan. Berikut ialah beberapa kaedah pengisihan biasa dan penerangannya:

Isih Buih

Isih Bubble ialah algoritma pengisihan mudah yang berulang kali merentasi tatasusunan untuk diisih, membandingkan dua elemen pada satu masa dan menukarnya jika ia berada dalam susunan yang salah. Kerja melintasi tatasusunan diulang sehingga tiada lagi pertukaran diperlukan, yang bermaksud tatasusunan telah diisih.

Kerumitan masa: O(n^2)

Isih Pemilihan

Isih Pilihan Ia adalah ringkas dan mudah algoritma pengisihan intuitif. Prinsip kerjanya ialah memilih elemen terkecil (atau terbesar) daripada elemen data untuk diisih setiap kali dan menyimpannya pada permulaan jujukan sehingga semua elemen data yang hendak diisih disusun.

Kerumitan masa: O(n^2)

Isih Sisipan

Isih Sisipan Ia adalah ringkas dan Isih algoritma pengisihan intuitif. Ia berfungsi dengan membina urutan tersusun Untuk data yang tidak diisih, ia mengimbas dari belakang ke hadapan dalam urutan yang diisih, mencari kedudukan yang sepadan dan memasukkannya.

Kerumitan masa: O(n^2)

Isih Cepat

Isih Cepat Menggunakan Prinsip Pembahagian dan menakluki, mula-mula pilih elemen pangsi, dan kemudian bahagikan semua elemen kepada dua bahagian Elemen dalam satu bahagian adalah lebih kecil daripada elemen pangsi, dan elemen di bahagian lain lebih besar daripada elemen pangsi. Kemudian cepat susun dua bahagian secara berasingan. Selepas rekursi selesai, keseluruhan urutan menjadi teratur.

Kerumitan masa: Purata kerumitan masa ialah O(n log n), dan kes terburuk ialah O(n^2).

Merge Sort

Merge sort juga merupakan algoritma pengisihan yang menggunakan prinsip bahagi dan takluk. Ia membahagikan tatasusunan kepada dua sub-tatasusunan, menggabungkan-mengisih dua sub-tatasusunan secara berasingan, dan kemudian menggabungkan hasilnya ke dalam tatasusunan tertib.

Kerumitan masa: Purata kerumitan masa ialah O(n log n), dan dalam kes yang paling teruk ialah O(n^2).

Isih Timbunan

Isih Timbunan ialah isihan pemilihan pokok, yang merupakan penambahbaikan yang berkesan pada jenis pemilihan langsung. Idea asasnya ialah untuk membina jujukan untuk diisih ke dalam timbunan atas yang besar Pada masa ini, nilai maksimum bagi keseluruhan jujukan ialah nod akar di bahagian atas timbunan. Kemudian tukar dengan elemen terakhir, iaitu nilai maksimum. Kemudian bina semula unsur n-1 yang tinggal ke dalam timbunan, supaya nilai n unsur terkecil seterusnya akan diperolehi. Jika anda melaksanakan ini berulang kali, anda boleh mendapatkan urutan tertib.

Kerumitan masa: O(n log n)

Mengira Isih

Mengira Isih Ia bukan perbandingan -algoritma pengisihan berasaskan dan kerumitannya ialah O(n). Ia ialah algoritma pengisihan kerumitan masa linear yang sesuai untuk mengisih integer dalam julat tertentu. Ia berfungsi dengan mengira bilangan kejadian setiap elemen dalam urutan yang hendak diisih, dan kemudian meletakkan elemen dalam kedudukan yang sepadan berdasarkan bilangan kejadian.

Kerumitan masa: O(n+k), dengan k ialah julat elemen yang hendak diisih.

Isih Baldi

Isih Baldi ialah algoritma pengisihan dengan kerumitan masa linear, sesuai untuk terapung dalam julat tertentu Isih titik. Prinsip kerjanya ialah membahagikan elemen untuk diisih kepada beberapa baldi, dan kemudian menggunakan algoritma seperti isihan pantas di dalam setiap baldi untuk mengisih. Akhir sekali, unsur-unsur dalam setiap baldi digabungkan ke dalam urutan tersusun mengikut tertib.

Kerumitan masa: Purata kerumitan masa ialah O(n), dan dalam kes yang paling teruk ialah O(n^2).

Ini adalah kaedah pengisihan biasa, setiap kaedah mempunyai senario, kelebihan dan kekurangan yang boleh digunakan. Dalam pengaturcaraan sebenar, adalah perlu untuk memilih algoritma pengisihan yang sesuai berdasarkan masalah dan data tertentu.

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