Isih pantas menggunakan Python

Isih cepat ialah algoritma pengisihan yang biasa digunakan dengan kerumitan masa O(nlogn). Dalam aplikasi praktikal, isihan pantas biasanya lebih pantas daripada algoritma pengisihan lain. Python menyediakan banyak fungsi pengisihan terbina dalam, tetapi masih penting untuk memahami dan melaksanakan quicksort. Dalam artikel ini, kami akan melaksanakan algoritma isihan pantas melalui Python.

Isih pantas berfungsi dengan memilih nilai pangsi (pangsi), kemudian meletakkan semua elemen dalam senarai yang lebih kecil daripada nilai pangsi dalam subsenarai dan meletakkan semua elemen yang lebih besar daripada nilai pangsi dalam subsenarai lain dalam senarai. Kedua-dua subsenarai kemudian diisih secara rekursif dengan cepat. Akhirnya, semua subsenarai akan diisih secara rekursif dan kemudian digabungkan menjadi satu senarai diisih.

Berikut ialah kod untuk melaksanakan isihan pantas dalam Python:

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

Dalam kod di atas, kami mula-mula menyemak panjang senarai. Jika panjang senarai kurang daripada 2, kami mengembalikan senarai asal. Jika tidak, kami memilih elemen pertama senarai sebagai nilai pangsi. Kami kemudian menggunakan pemahaman senarai untuk meletakkan elemen kurang daripada atau sama dengan nilai pangsi ke dalam satu senarai, dan elemen yang lebih besar daripada nilai pangsi ke dalam senarai lain. Seterusnya, kami mengisih senarai yang lebih kecil dan lebih besar secara rekursif dan menggabungkan senarai yang diisih bersama-sama, dengan nilai pangsi diletakkan di tengah-tengah senarai yang digabungkan.

Algoritma ini perlu memilih nombor rujukan yang sesuai. Jika nombor asas yang dipilih adalah nilai terbesar (atau terkecil) dalam senarai, maka saiz subsenarai yang diisih secara rekursif dikurangkan sebanyak 1 sahaja. Dalam kes ini, kerumitan masa algoritma isihan pantas mungkin merosot kepada O(n2). Untuk mengelakkan ini, kita boleh menggunakan kaedah memilih nilai asas secara rawak. Kaedah ini menjamin saiz subsenarai yang diisih secara rekursif secara purata dalam kes di mana nilai asas bukan nilai terbesar (atau terkecil) dalam senarai.

Berikut ialah kod Python untuk menggunakan pemilihan rawak bagi nilai penanda aras:

import random

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot_index = random.randint(0, len(arr) - 1)
        pivot = arr[pivot_index]
        less = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i <= pivot]
        greater = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

Dalam kod di atas, kami mula-mula memilih secara rawak nilai penanda aras menggunakan fungsi random.randint(). Kemudian, kami meletakkan elemen yang kurang daripada atau sama dengan nilai garis dasar ke dalam satu senarai, dan elemen yang lebih besar daripada nilai garis dasar ke dalam senarai lain, yang serupa dengan pelaksanaan sebelumnya.

Untuk meringkaskan, kami melaksanakan algoritma isihan pantas dalam Python dan menggunakan kaedah memilih nilai penanda aras secara rawak untuk mengelakkan ketidakseimbangan saiz subsenarai yang disusun secara rekursif. Algoritma ini berdasarkan idea Divide and Conquer, yang boleh mengisih senarai dengan cepat dengan kerumitan masa O(nlogn) secara purata.

Atas ialah kandungan terperinci Isih pantas menggunakan Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!