Bagaimana untuk melaksanakan algoritma jenis cepat dalam Python?

Bagaimana untuk melaksanakan algoritma isihan pantas dalam Python?

Isih cepat ialah algoritma pengisihan biasa dan cekap yang boleh mengisih senarai n elemen dengan kerumitan masa O(n log n) secara purata. Artikel ini akan memperkenalkan cara menggunakan Python untuk menulis contoh kod algoritma isihan pantas.

Idea asas isihan pantas ialah memilih elemen sebagai penanda aras (biasanya elemen pertama dalam senarai), bahagikan senarai itu kepada dua urutan, supaya semua elemen urutan kiri kurang daripada penanda aras, dan semua elemen urutan yang betul adalah lebih besar daripada penanda aras. Kemudian susulan kiri dan kanan dengan cepat diisih secara rekursif sehingga panjang susulan ialah 1 atau 0 dan pengisihan selesai.

Berikut ialah contoh kod untuk melaksanakan algoritma isihan pantas dalam Python:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]  # 选择第一个元素作为基准
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

Kod di atas mentakrifkan fungsi yang dipanggil quicksort, yang menerima arr senarai sebagai input dan mengembalikan senarai yang diisih. Pertama, jika panjang senarai input kurang daripada atau sama dengan 1, senarai itu dikembalikan terus, kerana senarai dengan panjang 0 atau 1 sudah dipesan.

Kemudian, pilih elemen pertama senarai sebagai pangsi asas dan tambahkan elemen senarai yang lain pada dua senarai yang baru dibuat, kurang dan lebih besar, supaya elemen dalam kurang adalah kurang daripada atau sama dengan pangsi, dan unsur-unsur dalam lebih besar adalah lebih besar daripada pangsi.

Akhir sekali, fungsi isihan pantas dipanggil secara rekursif untuk mengisih dengan cepat semakin kecil dan lebih besar, dan yang diisih kurang, pangsi dan lebih besar disambungkan bersama untuk mendapatkan hasil pengisihan akhir.

Berikut ialah contoh menguji isihan pantas:

arr = [4, 2, 8, 5, 1, 6, 7, 3]
sorted_arr = quicksort(arr)
print(sorted_arr)  # 输出：[1, 2, 3, 4, 5, 6, 7, 8]

Dalam contoh di atas, senarai input arr mengandungi 8 integer, dan hasil isihan yang diperoleh selepas isihan pantas ialah [1, 2, 3, 4, 5, 6 , 7, 8].

Ringkasan:
Melalui contoh kod di atas, kita dapat melihat bahawa agak mudah untuk melaksanakan algoritma isihan pantas dalam Python. Dengan memilih elemen rujukan, senarai dibahagikan kepada dua urutan, dan kemudian urutan disusun secara rekursif, dan akhirnya senarai tertib diperoleh. Isih cepat ialah algoritma pengisihan yang cekap yang digunakan secara meluas dalam aplikasi praktikal.

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