Bagaimana untuk menulis algoritma jenis sisipan dalam Python?

Bagaimana cara menulis algoritma isihan sisipan dalam Python?

Isihan sisipan ialah algoritma pengisihan yang mudah dan intuitif. Ideanya adalah untuk membahagikan tatasusunan untuk diisih kepada bahagian tersusun dan bahagian yang tidak tersusun Setiap kali, elemen dipilih daripada bahagian tidak tertib dan dimasukkan ke dalam kedudukan yang betul bahagian yang dipesan. Pelaksanaan algoritma isihan sisipan biasanya dilaksanakan dengan membandingkan dan menukar elemen beberapa kali, dan kerumitan masa ialah O(n^2).

Mari kita lihat cara menulis algoritma isihan sisipan dalam bahasa Python, serta contoh kod khusus.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]              # 当前待插入元素
        j = i - 1                 # 有序部分的最后一个元素索引

        # 将比key大的元素都向后移动一位
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key           # 将key插入正确位置

    return arr

Di atas ialah kod pelaksanaan khusus bagi algoritma isihan sisipan. Dalam fungsi utama, kita perlu menghantar arr tatasusunan untuk diisih dan mengembalikan hasil yang diisih.

Dalam gelung utama algoritma, kita bermula dari elemen kedua dan menggunakannya sebagai kunci elemen yang akan dimasukkan. Kami kemudian membandingkan kekunci dengan elemen terakhir bahagian yang diisih dan menggerakkan elemen lebih besar daripada kekunci satu kedudukan ke belakang sehingga kami menemui kedudukan kunci yang betul. Akhir sekali, kami memasukkan kunci ke lokasi yang betul.

Seterusnya, kita boleh menguji algoritma isihan sisipan ini.

arr = [9, 5, 1, 6, 8, 2]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

Hasil output ialah:

[1, 2, 5, 6, 8, 9]

Anda boleh melihat bahawa melalui algoritma isihan sisipan, kami berjaya menyusun tatasusunan input dalam tertib menaik.

Untuk meringkaskan, menulis algoritma isihan sisipan dalam Python tidaklah rumit. Kami hanya perlu memahami idea asas jenis sisipan, dan kemudian melaksanakan kod yang sepadan berdasarkan idea tersebut. Sudah tentu, untuk menjadikan kod lebih mantap dan serba boleh, kami juga boleh mengendalikan kes tepi, seperti tatasusunan kosong atau tatasusunan dengan hanya satu elemen.

Saya harap artikel ini dapat membantu anda memahami dan menguasai algoritma isihan sisipan!

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma jenis sisipan dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!