Penjelasan terperinci tentang pelaksanaan jenis pemilihan dalam Python

Penjelasan terperinci tentang algoritma isihan pemilihan dalam Python

Isihan pilihan ialah algoritma pengisihan yang mudah tetapi tidak cekap ialah mencari elemen terkecil (atau terbesar) daripada urutan yang akan diisih setiap kali akhir urutan yang diisih. Dengan mengulangi proses ini sehingga semua elemen diisih.

Langkah-langkah isihan pemilihan adalah seperti berikut:

1. Lintas urutan dan cari elemen terkecil (atau terbesar).
2. Tukar elemen terkecil (atau terbesar) dengan elemen pada kedudukan traversal semasa.
3. Ulang langkah 1 dan 2 sehingga keseluruhan urutan telah dilalui.

Mari terangkan algoritma isihan pemilihan secara terperinci dan berikan contoh kod khusus.

Pertama, kami mentakrifkan fungsi untuk melaksanakan pengisihan pemilihan:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 找到未排序序列中的最小元素的索引
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # 将最小元素与当前遍历位置的元素交换
        arr[i], arr[min_index] = arr[min_index], arr[i]

Sekarang, mari kita uji kesan pengisihan pemilihan:

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

Jalankan kod di atas, output adalah seperti berikut:

排序后的数组:
11
12
22
25
64

Anda boleh melihat bahawa pengisihan pemilihan akan berjaya.

Kerumitan masa isihan pemilihan ialah O(n^2), dengan n ialah panjang jujukan yang hendak diisih. Ini kerana setiap kali anda perlu merentasi semua elemen dalam urutan tidak diisih untuk mencari elemen terkecil (atau terbesar), anda perlu melakukan n perbandingan. Sejumlah n-1 pusingan traversal perlu dilakukan, jadi kerumitan masa ialah O(n^2).

Isihan pilihan ialah algoritma pengisihan yang tidak stabil, iaitu susunan relatif bagi elemen yang sama mungkin berubah. Ini kerana isihan pemilihan dilaksanakan dengan menukar kedudukan elemen secara berterusan. Sebagai contoh, untuk jujukan [3, 1, 3], hasil yang mungkin selepas mengisih menggunakan algoritma isihan pemilihan ialah [1, 3, 3], dan kedudukan relatif unsur yang sama pada asalnya 3 telah berubah.

Walaupun jenis pemilihan kurang cekap, pelaksanaannya adalah mudah dan intuitif. Dalam beberapa kes tertentu, seperti apabila urutan yang hendak diisih adalah kecil atau keperluan kestabilan tidak tinggi, pengisihan pemilihan boleh digunakan sebagai kaedah pengisihan yang mudah.

Untuk meringkaskan, isihan pemilihan ialah algoritma yang melengkapkan pengisihan dengan terus mencari elemen terkecil (atau terbesar) dalam urutan yang tidak diisih dan menukarnya dengan elemen pada kedudukan traversal semasa. Walaupun pelaksanaannya mudah, kerumitan masa adalah tinggi dan tidak stabil. Dalam aplikasi praktikal, senario penggunaan pengisihan pemilihan agak terhad.

Atas ialah kandungan terperinci Penjelasan terperinci tentang pelaksanaan jenis pemilihan dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!