Bagaimana untuk mengisih dalam python

Kaedah pengisihan python termasuk isihan gelembung, isihan pemilihan, isihan sisipan, isihan pantas, isihan gabung, isihan timbunan, isihan radix, dsb. Pengenalan terperinci: 1. Pengisihan buih, pengisihan dengan membandingkan unsur-unsur bersebelahan dan bertukar-tukar kedudukannya; memasukkan setiap elemen ke dalam kedudukan yang sesuai bagi bahagian yang diisih;

Sistem pengendalian untuk tutorial ini: sistem Windows 10, Python versi 3.11.4, komputer Dell G3.

Python ialah bahasa pengaturcaraan berkuasa yang menyediakan pelbagai kaedah pengisihan untuk mengisih data. Dalam artikel ini, kami akan membincangkan sekurang-kurangnya 7 kaedah pengisihan berbeza, dengan contoh kod terperinci.

1. Isih Buih:

Isih buih ialah algoritma pengisihan mudah yang membandingkan elemen bersebelahan dan menukar kedudukannya. Ia berulang melalui senarai berulang kali sehingga tiada pertukaran berlaku.

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

2. Isih Pemilihan:

Isih pilihan ialah algoritma pengisihan mudah yang mencari elemen terkecil dalam senarai dan meletakkannya pada penghujung bahagian yang diisih.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

3. Isih Sisipan:

Isihan sisipan ialah algoritma pengisihan mudah yang memasukkan setiap elemen ke dalam kedudukan yang sesuai bagi bahagian yang diisih untuk diisih.

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

4 Isih Pantas:

Isih cepat ialah algoritma pengisihan yang cekap yang menggunakan kaedah bahagi-dan-takluk untuk membahagikan senarai kepada subsenarai yang lebih kecil, dan kemudian mengisih senarai. 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 Isih Gabung:

Isih Gabung ialah algoritma pengisihan yang cekap yang menggunakan kaedah bahagi-dan-takluk untuk membahagikan senarai kepada subsenarai yang lebih kecil, kemudian mengisih secara rekursif. subsenarai, dan akhirnya menggabungkannya ke dalam senarai tersusun.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    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. Isih Timbunan:

Isih Timbunan ialah algoritma isihan yang cekap yang menggunakan struktur data timbunan binari untuk pengisihan.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    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

7. Isih Radix:

Isihan Radix ialah algoritma isihan bukan perbandingan yang mengisih unsur berdasarkan bilangan digit.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    for i in range(1, 10):
        count[i] += count[i-1]
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    for i in range(n):
        arr[i] = output[i]
def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

Ini ialah contoh kod terperinci bagi 7 kaedah pengisihan yang berbeza. Mengikut set data dan keperluan prestasi yang berbeza, memilih algoritma pengisihan yang sesuai boleh meningkatkan kecekapan dan prestasi kod

Atas ialah kandungan terperinci Bagaimana untuk mengisih dalam python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!