目錄

1 冒泡排序（Bubble Sort）

2 插入排序（Insertion Sort）

3 選擇排序（Selection Sort）

4. 快速排序（Quick Sort）

5. 歸并排序（Merge Sort）

6 堆排序 (Heap Sort)

7 計(jì)數(shù)排序 (Counting Sort)

8 基數(shù)排序 (Radix Sort)

9 希爾排序（Shell Sort）

10 桶排序

? ?

1 冒泡排序（Bubble Sort）

???????冒泡排序是一種基本的排序算法，其核心思想是多次遍歷待排序的元素，比較相鄰的兩個元素，如果它們的順序不正確，則交換它們，直到整個數(shù)組按照指定順序排列。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            # 比較相鄰的兩個元素
            if arr[j] > arr[j+1]:
                # 如果順序不正確，則交換它們
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("冒泡排序后的數(shù)組：", arr)

????????冒泡排序通過多次遍歷數(shù)組，每次比較相鄰的兩個元素，如果它們的順序不正確就交換它們。這個過程將最大的元素逐漸“冒泡”到數(shù)組的末尾。

????????

????????時間復(fù)雜度為 O(n^2)，不適合大規(guī)模數(shù)據(jù)集。?

2 插入排序（Insertion Sort）

????????插入排序是一種穩(wěn)定的排序算法，其核心思想是將未排序的元素逐個插入到已排序的部分，從前往后遍歷，保持前面的元素有序。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            # 將較大的元素向右移動
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("插入排序后的數(shù)組：", arr)

????????插入排序逐個將未排序的元素插入到已排序的部分，從前往后遍歷，保持前面的元素有序。時間復(fù)雜度為 O(n^2)，適合小規(guī)模數(shù)據(jù)集和部分有序的數(shù)據(jù)。?

3 選擇排序（Selection Sort）

????????選擇排序是一種簡單的不穩(wěn)定排序算法，其核心思想是找到未排序部分的最小元素，將其與未排序部分的第一個元素交換位置。

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

# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("選擇排序后的數(shù)組：", arr)

? ? ? 選擇排序通過多次選擇未排序部分的最小元素，并將其與未排序部分的第一個元素交換位置來進(jìn)行排序。時間復(fù)雜度為 O(n^2)，不適合大規(guī)模數(shù)據(jù)集。

4. 快速排序（Quick Sort）

????????快速排序是一種高效的分治排序算法，它選擇一個基準(zhǔn)元素，將數(shù)組分成兩部分，左邊的元素都小于基準(zhǔn)，右邊的元素都大于基準(zhǔn)，然后遞歸對左右兩部分進(jìn)行排序。

def quick_sort(arr):
    # 基本情況：如果數(shù)組為空或只包含一個元素，無需排序
    if len(arr) <= 1:
        return arr
    
    # 選擇中間元素作為基準(zhǔn)點(diǎn)（pivot）
    pivot = arr[len(arr) // 2]
    
    # 將數(shù)組分成三部分：小于、等于、大于基準(zhǔn)點(diǎn)的元素
    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]
    
    # 遞歸排序左右兩部分，然后合并結(jié)果
    return quick_sort(left) + middle + quick_sort(right)

# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
arr = quick_sort(arr)
print("快速排序后的數(shù)組：", arr)

• 快速排序是一種高效的分治排序算法，它通過選擇一個基準(zhǔn)點(diǎn)（通常是數(shù)組中的中間元素）將數(shù)組分成左右兩部分，并遞歸地對左右兩部分進(jìn)行排序。
• 基本情況是數(shù)組為空或只包含一個元素，無需排序。
• 針對每個元素，將它與基準(zhǔn)點(diǎn)進(jìn)行比較，分成小于、等于和大于基準(zhǔn)點(diǎn)的三個子數(shù)組。
• 然后，遞歸地對左右兩部分進(jìn)行排序，最后將它們與基準(zhǔn)點(diǎn)合并，形成一個有序的數(shù)組。

5. 歸并排序（Merge Sort）

????????歸并排序是一種穩(wěn)定的分治排序算法，它將數(shù)組分成兩半，分別排序，然后將已排序的兩個子數(shù)組合并成一個有序數(shù)組。

def merge_sort(arr):
    # 基本情況：如果數(shù)組為空或只包含一個元素，無需排序
    if len(arr) <= 1:
        return arr
    
    # 將數(shù)組分成兩半
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # 遞歸地對左右兩部分進(jìn)行排序
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 合并已排序的左右兩部分
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    # 合并兩個已排序的子數(shù)組
    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
    
    # 如果左邊或右邊的子數(shù)組還有剩余元素，將它們添加到結(jié)果中
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
arr = merge_sort(arr)
print("歸并排序后的數(shù)組：", arr)

• 歸并排序是一種穩(wěn)定的分治排序算法，它將數(shù)組遞歸分成兩半，然后合并已排序的子數(shù)組。
• 基本情況是數(shù)組為空或只包含一個元素，無需排序。
• 遞歸地對左右兩部分進(jìn)行排序，然后使用 merge 函數(shù)將它們合并成一個有序的數(shù)組。
• merge 函數(shù)將兩個已排序的子數(shù)組合并，同時維護(hù)它們的有序性。

6 堆排序 (Heap Sort)

????????堆排序是一種不穩(wěn)定的排序算法，它使用堆數(shù)據(jù)結(jié)構(gòu)（通常是最大堆）來進(jìn)行排序。堆排序分為兩個主要步驟：建立堆和排序。

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    # 找到左子節(jié)點(diǎn)和右子節(jié)點(diǎn)中的最大值
    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是當(dāng)前節(jié)點(diǎn)，交換它們
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]

def heap_sort(arr):
    n = len(arr)

    # 構(gòu)建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 一個接一個地從堆中取出元素，交換根節(jié)點(diǎn)與最后一個節(jié)點(diǎn)，然后重新構(gòu)建堆
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
heap_sort(arr)
print("堆排序后的數(shù)組：", arr)

• 排序使用堆數(shù)據(jù)結(jié)構(gòu)（通常是最大堆）來進(jìn)行排序。首先構(gòu)建最大堆，然后一個接一個地從堆中取出元素，交換根節(jié)點(diǎn)與最后一個節(jié)點(diǎn)，然后重新構(gòu)建堆。
• heapify 函數(shù)用于維護(hù)堆的性質(zhì)，即父節(jié)點(diǎn)的值大于或等于子節(jié)點(diǎn)的值。
• 這個算法的時間復(fù)雜度為 O(nlogn)，是一種高效的排序算法。

7 計(jì)數(shù)排序 (Counting Sort)

????????計(jì)數(shù)排序是一種非比較排序算法，它根據(jù)輸入元素的計(jì)數(shù)來對元素進(jìn)行排序。它適用于整數(shù)或有限范圍內(nèi)的非負(fù)整數(shù)。

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_of_elements = max_val - min_val + 1
    count_arr = [0] * range_of_elements
    output_arr = [0] * len(arr)

    # 計(jì)數(shù)每個元素的出現(xiàn)次數(shù)
    for num in arr:
        count_arr[num - min_val] += 1

    # 計(jì)算每個元素的累積計(jì)數(shù)
    for i in range(1, len(count_arr)):
        count_arr[i] += count_arr[i - 1]

    # 根據(jù)累積計(jì)數(shù)將元素放入輸出數(shù)組
    for i in range(len(arr) - 1, -1, -1):
        output_arr[count_arr[arr[i] - min_val] - 1] = arr[i]
        count_arr[arr[i] - min_val] -= 1

    return output_arr

# 示例用法
arr = [4, 2, 2, 8, 3, 3, 1]
arr = counting_sort(arr)
print("計(jì)數(shù)排序后的數(shù)組：", arr)

• 計(jì)數(shù)排序是一種非比較排序算法，適用于整數(shù)或有限范圍內(nèi)的非負(fù)整數(shù)。
• 首先，計(jì)算每個元素的出現(xiàn)次數(shù)，然后計(jì)算每個元素的累積計(jì)數(shù)，最后根據(jù)累積計(jì)數(shù)將元素放入輸出數(shù)組。
• 這個算法的時間復(fù)雜度為 O(n+k)，其中 k 是輸入范圍的大小。?

8 基數(shù)排序 (Radix Sort)

????????基數(shù)排序是一種非比較排序算法，它將數(shù)字按照每個位數(shù)進(jìn)行排序，從最低位到最高位，依次排列。

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # 計(jì)數(shù)每個元素的出現(xiàn)次數(shù)
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    # 計(jì)算每個元素的累積計(jì)數(shù)
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 根據(jù)累積計(jì)數(shù)將元素放入輸出數(shù)組
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    # 將輸出數(shù)組的內(nèi)容復(fù)制到原始數(shù)組中
    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

# 示例用法
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("基數(shù)排序后的數(shù)組：", arr)

• 基數(shù)排序是一種非比較排序算法，它按照每個位數(shù)進(jìn)行排序，從最低位到最高位，依次排列。
• 首先使用計(jì)數(shù)排序?qū)γ總€位數(shù)進(jìn)行排序，然后再次對下一個位數(shù)進(jìn)行排序，依次進(jìn)行直到最高位。
• 這個算法的時間復(fù)雜度為 O(nk)，其中 k 是數(shù)字的最大位數(shù)。

9 希爾排序（Shell Sort）

????????希爾排序（Shell Sort）是一種插入排序的改進(jìn)版本，也被稱為縮小增量排序。希爾排序通過將數(shù)組分成若干個子序列來排序數(shù)據(jù)，然后逐漸縮小子序列的間隔，最終得到一個完全排序的數(shù)組。希爾排序的主要思想是提前交換較遠(yuǎn)的元素，以加快排序過程。

算法原理：

1. 選擇一個增量序列（間隔序列），通常選擇的增量是數(shù)組長度的一半，然后逐漸減小增量。

2. 對于每個增量，將數(shù)組分成若干個子序列，每個子序列使用插入排序進(jìn)行排序。

3. 重復(fù)步驟2，逐漸減小增量，直到增量為1。

4. 當(dāng)增量為1時，整個數(shù)組成為一個序列，使用插入排序?qū)ζ溥M(jìn)行排序。

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始增量取數(shù)組長度的一半

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # 使用插入排序?qū)ψ有蛄羞M(jìn)行排序
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # 縮小增量

# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
shell_sort(arr)
print("希爾排序后的數(shù)組：", arr)

?????????希爾排序的關(guān)鍵在于選擇合適的增量序列。常見的增量序列有希爾增量、Hibbard增量、Knuth增量等，不同的增量序列會影響排序的性能。

• 希爾排序的時間復(fù)雜度取決于增量序列的選擇，平均時間復(fù)雜度通常在 O(n^1.25) 到 O(n^2) 之間，比插入排序要快。

• 希爾排序是一種不穩(wěn)定排序算法，適用于中等大小的數(shù)據(jù)集。雖然不如快速排序和歸并排序快，但在某些情況下比插入排序更快。希爾排序通常用于嵌入式系統(tǒng)等資源有限的環(huán)境。

10 桶排序（Bucket Sort）

?????????桶排序（Bucket Sort）是一種分布式排序算法，它將元素分散到一組桶中，然后對每個桶中的元素進(jìn)行排序，最后將所有桶中的元素按順序合并成一個有序序列。桶排序適用于元素均勻分布在一個范圍內(nèi)的情況，特別適用于浮點(diǎn)數(shù)排序。

算法原理：

1. 確定桶的數(shù)量和范圍，通常根據(jù)輸入數(shù)據(jù)的分布來選擇桶的數(shù)量。如果元素均勻分布在一個范圍內(nèi)，那么可以選擇桶的數(shù)量等于元素的數(shù)量。

2. 將每個元素分配到相應(yīng)的桶中。元素的分配可以采用不同的方法，例如線性劃分或哈希函數(shù)。

3. 對每個桶中的元素進(jìn)行排序，可以使用任何排序算法，通常選擇插入排序。

4. 合并所有桶中的元素，按照桶的順序得到最終的有序序列。

def bucket_sort(arr):
    # 確定桶的數(shù)量，這里選擇與輸入元素?cái)?shù)量相同
    n = len(arr)
    if n <= 1:
        return arr

    # 初始化桶
    max_val = max(arr)
    min_val = min(arr)
    bucket_range = (max_val - min_val) / n  # 每個桶的范圍
    bucket_count = n  # 桶的數(shù)量等于元素?cái)?shù)量
    buckets = [[] for _ in range(bucket_count)]

    # 將元素分配到桶中
    for num in arr:
        index = int((num - min_val) / bucket_range)
        buckets[index].append(num)

    # 對每個桶中的元素進(jìn)行排序
    for i in range(bucket_count):
        buckets[i].sort()

    # 合并所有桶中的元素
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr

# 示例用法
arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
arr = bucket_sort(arr)
print("桶排序后的數(shù)組：", arr)

?????????桶排序的性能取決于桶的數(shù)量和元素的分布。如果元素均勻分布在一個范圍內(nèi)，并且桶的數(shù)量足夠多，那么桶排序可以非常高效。

• 桶排序的時間復(fù)雜度通常為 O(n + k)，其中 n 是元素的數(shù)量，k 是桶的數(shù)量。

• 桶排序是一種穩(wěn)定排序算法，適用于浮點(diǎn)數(shù)排序等特定情況。不過，它需要額外的內(nèi)存空間來存儲桶，因此不適用于數(shù)據(jù)集非常大的情況。文章來源地址http://www.zghlxwxcb.cn/news/detail-718297.html

到了這里，關(guān)于【Python排序算法】一文掌握十大排序算法，冒泡排序、插入排序、選擇排序、歸并排序、計(jì)數(shù)排序、基數(shù)排序、希爾排序和堆排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！