Pelajari dan laksanakan algoritma isihan pemilihan dalam Python

Fahami prinsip dan pelaksanaan isihan pemilihan dalam Python

Isih Pilihan ialah algoritma pengisihan yang mudah dan intuitif ialah melintasi tatasusunan setiap kali dan memilih yang terkecil (atau terbesar) dalam bahagian yang tidak diisih , tukar kedudukannya dengan elemen pertama bahagian yang tidak diisih, dan kemudian teruskan memilih elemen terkecil (atau terbesar) daripada bahagian yang tidak diisih, dan seterusnya, sehingga keseluruhan tatasusunan diisih. Kerumitan masa isihan pemilihan ialah O(n^2), dan ia merupakan algoritma pengisihan yang tidak stabil.

Yang berikut menggunakan contoh kod khusus untuk menggambarkan proses pelaksanaan pengisihan pemilihan.

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Di atas ialah kod pelaksanaan algoritma isihan pemilihan. Seterusnya kami akan menerangkan prinsip dan proses kod ini langkah demi langkah.

Pertama, kami mentakrifkan fungsi selection_sort, yang menerima arr tatasusunan untuk diisih sebagai parameter.

Dalam badan fungsi, kita mula-mula mendapat panjang n tatasusunan Ini adalah untuk mengulang n-1 kali, kerana setiap lelaran akan meletakkan elemen terkecil dalam kedudukan yang betul, jadi elemen terakhir tidak perlu diisih.

Kemudian, kami menggunakan dua gelung bersarang untuk melaksanakan proses pengisihan pemilihan. Gelung luar pergi dari 0 hingga n-1, mewakili kedudukan permulaan i bahagian yang hendak diisih.

Gelung dalam ialah dari i+1 hingga n, mewakili unsur j dalam bahagian yang hendak diisih. Kami membandingkan j dengan elemen pada kedudukan permulaan i Jika j lebih kecil daripada elemen pada kedudukan permulaan i, min_idx dikemas kini kepada j, menunjukkan bahawa j ialah indeks unsur terkecil yang ditemui setakat ini.

Apabila gelung dalam tamat, kami akan menukar kedudukan elemen terkecil yang ditemui dengan elemen pada kedudukan permulaan i, supaya lelaran semasa akan meletakkan elemen terkecil pada kedudukan yang betul.

Dengan lelaran n-1, kami boleh memastikan keseluruhan tatasusunan diisih dalam tertib menaik.

Seterusnya, kita boleh menggunakan kod berikut untuk menguji kesan isihan pemilihan:

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组：")
for i in range(len(arr)):
    print(arr[i], end=" ")

Hasil output ialah: 11 12 22 25 64, yang bermaksud tatasusunan telah diisih dalam tertib menaik.

Dalam penggunaan sebenar, isihan pemilihan adalah kurang cekap, jadi kami lebih suka menggunakan algoritma pengisihan lain yang lebih cekap, seperti isihan cepat atau isihan gabungan. Walau bagaimanapun, pengisihan pemilihan ialah algoritma pengisihan yang mudah dan mudah difahami, yang membantu pemula untuk memahami prinsip asas dan idea algoritma pengisihan.

Ringkasnya, pengisihan pemilihan ialah memilih elemen terkecil (atau terbesar) daripada bahagian yang tidak diisih setiap kali, meletakkannya di hujung bahagian yang diisih, dan melalui berbilang lelaran, akhirnya mencapai tujuan memesan keseluruhan tatasusunan. Menguasai prinsip dan pelaksanaan jenis pemilihan adalah sangat penting untuk pemahaman yang mendalam tentang algoritma pengisihan dan peningkatan kebolehan pengaturcaraan.

Atas ialah kandungan terperinci Pelajari dan laksanakan algoritma isihan pemilihan dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!