Apakah algoritma pengisihan dalam Python?

Algoritma pengisihan yang biasa digunakan dalam Python termasuk isihan gelembung, isihan sisipan, isihan pemilihan, isihan pantas, isihan gabung dan isihan timbunan. Prinsip-prinsip algoritma pengisihan ini akan diperkenalkan di bawah, dan contoh kod yang sepadan akan diberikan.

1. Isih Buih:
   Isih Buih ialah algoritma pengisihan yang mudah dan intuitif. Ia berulang kali merentasi senarai untuk diisih, membandingkan saiz dua elemen bersebelahan, dan menggerakkan elemen yang lebih besar ke belakang. Semasa setiap lelaran, elemen terbesar "gelembung" ke penghujung senarai.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2. Isihan sisipan:
   Idea asas isihan sisipan ialah memasukkan unsur-unsur yang hendak diisih ke dalam kedudukan yang betul satu demi satu dalam senarai yang diisih. Isih sisipan bermula dari elemen kedua, membandingkan setiap elemen dengan senarai diisih sebelumnya dan memasukkannya ke dalam kedudukan yang sesuai.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

3. Isih Pilihan:
   Isih pilihan merentasi senarai setiap kali, mencari elemen terkecil dan menukarnya dengan kedudukan semasa. Teruskan mengulangi proses ini sehingga keseluruhan senarai diisih.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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]
    return arr

4. Isih Pantas:
   Isih Pantas ialah algoritma pengisihan yang cekap. Ia menggunakan idea Divide dan Conquer untuk membahagikan senarai kepada dua subsenarai, dan kemudian mengisih subsenarai secara rekursif.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

5. Gabung isihan:
   Gabung isihan membahagikan senarai kepada dua subsenarai, mengisih setiap subsenarai, dan kemudian menggabungkan subsenarai yang diisih bersama-sama.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

6. Isihan timbunan:
   Isihan timbunan ialah algoritma isihan pemilihan pokok yang menggunakan sifat timbunan binari untuk mengisih. Timbunan boleh dibahagikan kepada timbunan maks dan timbunan min Nod akar timbunan maks ialah elemen terbesar, dan nod akar timbunan min ialah unsur terkecil.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[i] < arr[left]:
        largest = left
    if right < n and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

Di atas ialah beberapa algoritma pengisihan yang biasa digunakan dalam Python, dan contoh kod yang sepadan disediakan. Algoritma pengisihan yang berbeza sesuai untuk situasi dan saiz data yang berbeza Memilih algoritma pengisihan yang sesuai mengikut situasi sebenar boleh meningkatkan kecekapan pengendalian program.

Atas ialah kandungan terperinci Apakah algoritma pengisihan dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!