Panduan pelaksanaan dan pengoptimuman untuk jenis pemilihan Python

Langkah dan kaedah pengoptimuman isihan pemilihan Python

Isih Pemilihan ialah algoritma pengisihan yang mudah dan intuitif. Idea asasnya ialah untuk memilih elemen terkecil (atau terbesar) daripada elemen data untuk diisih setiap kali, menyimpannya pada permulaan jujukan, dan kemudian terus mencari elemen terkecil (atau terbesar) daripada elemen yang tidak diisih yang tinggal. , diletakkan di hujung urutan yang diisih. Ulangi proses ini sehingga semua elemen data yang hendak diisih disusun.

Langkah-langkah pengisihan pemilihan boleh diringkaskan seperti berikut:

1. Lintas urutan yang hendak diisih dan tandakan kedudukan semasa sebagai kedudukan elemen terkecil.
2. Cari elemen yang lebih kecil daripada elemen terkecil semasa daripada elemen di belakang kedudukan yang ditanda, dan kemas kini kedudukan yang ditanda.
3. Tukar elemen pada kedudukan yang ditanda dengan elemen pada kedudukan elemen minimum.
4. Gunakan elemen selepas kedudukan yang ditanda sebagai kedudukan permulaan yang baharu dan ulangi langkah 2 dan 3.

Kaedah pengoptimuman isihan pemilihan ialah:

1. Dalam setiap lintasan, cari elemen minimum dan elemen maksimum pada masa yang sama, dan tukarkannya pada masa yang sama. Ini boleh mengurangkan bilangan pertukaran dan meningkatkan kecekapan pengisihan.
2. Tambah pertimbangan Jika tiada pertukaran berlaku semasa proses traversal iaitu pengisihan telah selesai, proses pengisihan akan ditamatkan lebih awal.

Berikut ialah contoh kod isihan pemilihan dalam Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_pos = i
        max_pos = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_pos]:
                min_pos = j
            if arr[j] > arr[max_pos]:
                max_pos = j
        if min_pos != i:
            arr[i], arr[min_pos] = arr[min_pos], arr[i]
        if max_pos == i:
            max_pos = min_pos
        if max_pos != n - 1 - i:
            arr[n - 1 - i], arr[max_pos] = arr[max_pos], arr[n - 1 - i]
        if min_pos == n - 1 - i:
            min_pos = max_pos
        if min_pos != i:
            arr[i], arr[min_pos] = arr[min_pos], arr[i]
    return arr

# 测试
arr = [64, 25, 12, 22, 11]
print("排序前:", arr)
sorted_arr = selection_sort(arr)
print("排序后:", sorted_arr)

Dalam kod di atas, kedudukan pembolehubah min_pos 记录最小元素的位置，使用变量 max_pos 记录最大元素的位置。在每次遍历中，通过比较更新这两个位置，然后进行交换。在列表长度为奇数时，如果 min_pos 和 max_pos yang kita gunakan berlaku bertepatan dengan kedudukan permulaan, dan kita perlu menyemak dan memproses kedudukan yang ditukar.

Di atas ialah langkah dan kaedah pengoptimuman pengisihan pemilihan Python, serta contoh kod khusus. Walaupun pengisihan pemilihan adalah mudah, ia kurang cekap dan mempunyai kerumitan masa O(n^2). Oleh itu, dalam aplikasi praktikal, jika skala pengisihan adalah besar, adalah disyorkan untuk menggunakan algoritma pengisihan yang lebih cekap, seperti isihan cepat atau isihan gabungan.

Atas ialah kandungan terperinci Panduan pelaksanaan dan pengoptimuman untuk jenis pemilihan Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!