国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<address id="wthyf"><tr id="wthyf"></tr></address><track id="wthyf"></track>

^{<meter id="wthyf"></meter>}

八大排序算法 (python版本)

2年前作者：CodeWang_NC分類：Toy博客閱讀(16)違法舉報

這篇具有很好參考價值的文章主要介紹了八大排序算法 (python版本)。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

八大排序算法

個人學習筆記 如有問題歡迎指正交流

快速排序經(jīng)常考，如果只掌握一個排序算法的話，首選快速排序算法
八大排序算法通常指的是以下八種經(jīng)典排序算法：

1. 冒泡排序 (Bubble Sort)

使用場景：適用于小規(guī)模數(shù)據(jù)的排序，不推薦用于大規(guī)模數(shù)據(jù)排序。
穩(wěn)定性：穩(wěn)定排序算法。
時間復(fù)雜度：平均和最壞情況下 O(n^2)，最好情況下 O(n)（當輸入數(shù)據(jù)已經(jīng)有序時）。

2. 選擇排序 (Selection Sort):

使用場景：適用于小規(guī)模數(shù)據(jù)的排序，與冒泡排序類似，不適用于大規(guī)模數(shù)據(jù)排序。
穩(wěn)定性：不穩(wěn)定排序算法。
時間復(fù)雜度：都為 O(n^2)。

3. 插入排序 (Insertion Sort):

使用場景：適用于小規(guī)模數(shù)據(jù)，也適用于部分有序的大規(guī)模數(shù)據(jù)。
穩(wěn)定性：穩(wěn)定排序算法。
時間復(fù)雜度：平均和最壞情況下 O(n^2)，最好情況下 O(n)（當輸入數(shù)據(jù)已經(jīng)有序時）。

4. 希爾排序 (Shell Sort):

使用場景：適用于中等規(guī)模數(shù)據(jù)，對于大規(guī)模數(shù)據(jù)效果也不錯。
穩(wěn)定性：不穩(wěn)定排序算法。
時間復(fù)雜度：最壞情況下取決于間隔序列，通常介于 O(n log n) 和 O(n^2) 之間。

5. 歸并排序 (Merge Sort):

使用場景：適用于大規(guī)模數(shù)據(jù)，對數(shù)據(jù)規(guī)模不敏感，效率穩(wěn)定。
穩(wěn)定性：穩(wěn)定排序算法。
時間復(fù)雜度：始終為 O(n log n)，但需要額外的空間來存儲中間結(jié)果。

6. 快速排序 (Quick Sort):

使用場景：適用于大規(guī)模數(shù)據(jù)，且在大多數(shù)情況下效率較高。
穩(wěn)定性：不穩(wěn)定排序算法。
時間復(fù)雜度：平均情況下 O(n log n)，最壞情況下 O(n^2)（當選擇的主元極不均勻時）。

7. 堆排序 (Heap Sort):

使用場景：適用于大規(guī)模數(shù)據(jù)，且對內(nèi)存要求較高，適合外部排序。
穩(wěn)定性：不穩(wěn)定排序算法。
時間復(fù)雜度：始終為 O(n log n)，且不需要額外空間。

8. 計數(shù)排序 (Counting Sort):

使用場景：適用于數(shù)據(jù)范圍不大，但是數(shù)據(jù)量較大的情況。
穩(wěn)定性：穩(wěn)定排序算法。
時間復(fù)雜度：最好情況下為 O(n + k)，其中 k 表示數(shù)據(jù)范圍。

每種排序算法都有其獨特的應(yīng)用場景和特點，根據(jù)實際問題選擇合適的排序算法能夠有效提高程序的效率。

1. 冒泡排序

八大排序算法 (python版本),LeetCode,排序算法,python,算法

圖1摘自菜鳥教程

冒泡排序(相鄰比較冒泡) 遍歷i時 (0, n-i)進行比較 (n-i, n)是有序的
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
  針對所有的元素重復(fù)以上的步驟，除了最后一個。

復(fù)雜度: O(n^2)
穩(wěn)定性：穩(wěn)定排序算法。
使用場景：適用于小規(guī)模數(shù)據(jù)的排序，不推薦用于大規(guī)模數(shù)據(jù)排序。
詳細介紹: https://www.runoob.com/w3cnote/bubble-sort.html
視頻講解: https://www.bilibili.com/video/BV1Hg4y1q7tz

"""
1.冒泡排序(相鄰比較冒泡) 遍歷i次之后 (0, n-i)進行比較 (n-i, n)是有序的
    1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
    2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
    針對所有的元素重復(fù)以上的步驟，除了最后一個。
復(fù)雜度: O(n^2)
穩(wěn)定性：穩(wěn)定排序算法。
使用場景：適用于小規(guī)模數(shù)據(jù)的排序，不推薦用于大規(guī)模數(shù)據(jù)排序。
詳細介紹: https://www.runoob.com/w3cnote/bubble-sort.html
視頻講解: https://www.bilibili.com/video/BV1Hg4y1q7tz
"""
def bubble_sort(arr):
    for i in range(len(arr)):
        flag = True
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = False
        if flag:
            break
    return arr

if __name__ == '__main__':
    arr = [5, 4, 3, 2, 1]
    res = bubble_sort(arr)
    print(f"res: {res}")

2. 選擇排序

八大排序算法 (python版本),LeetCode,排序算法,python,算法

圖2摘自菜鳥教程

選擇排序遍歷i次之后操作(0, i)是有序的 (i, n) 進行比較
(選擇最小(最大)的在未排序的最開始(末尾)位置) 針對(i, n)進行的排序
1. 在每一輪循環(huán)中，找到未排序部分中的最小元素的索引，然后將最小元素與當前位置進行交換。
2. 每一輪循環(huán)會將一個最小元素放到已排序部分的末尾。

復(fù)雜度: O(n^2)
穩(wěn)定性：不穩(wěn)定排序算法。
使用場景：適用于小規(guī)模數(shù)據(jù)的排序，與冒泡排序類似，不適用于大規(guī)模數(shù)據(jù)排序。
詳細介紹: https://www.runoob.com/w3cnote/selection-sort.html
視頻講解: https://www.bilibili.com/video/BV1VK4y1475t

"""
2.選擇排序 遍歷i次之后 操作(0, i)是有序的 (i, n) 進行比較
    (選擇最小(最大)的在未排序的最開始(末尾)位置) 針對(i, n)進行的排序
    1.在每一輪循環(huán)中，找到未排序部分中的最小元素的索引，然后將最小元素與當前位置進行交換。
    2.每一輪循環(huán)會將一個最小元素放到已排序部分的末尾。
復(fù)雜度: O(n^2)
穩(wěn)定性：不穩(wěn)定排序算法。
使用場景：適用于小規(guī)模數(shù)據(jù)的排序，與冒泡排序類似，不適用于大規(guī)模數(shù)據(jù)排序。
詳細介紹: https://www.runoob.com/w3cnote/selection-sort.html
視頻講解: https://www.bilibili.com/video/BV1VK4y1475t
"""
def select_sort(arr):
    # l = 0
    n = len(arr)
    for i in range(n):
        min_index = i
        min = arr[i]
        for j in range(i+1, n):
            if arr[j] < min:
                min = arr[j]
                min_index = j
        print(f"l:flag_index {i}:{min_index}")
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr
if __name__ == '__main__':
    arr = [9, 5, 2, 7, 12, 4]
    print(f"before: {arr}")
    res = select_sort(arr)
    print(f"res: {res}")

3. 插入排序

八大排序算法 (python版本),LeetCode,排序算法,python,算法

圖2摘自菜鳥教程

插入排序
遍歷i時 (0, i-1)是有序的將i插入到(0, i-1)序列中 (i, n)無序的
找到一個合適的所用在(0, i-1) 中找到一個合適的位置進行插入
1. 在每一輪循環(huán)中，找到未排序部分中的最小元素的索引，然后將最小元素與當前位置進行交換。
2. 每一輪循環(huán)會將一個最小元素放到已排序部分的末尾。

復(fù)雜度: O(n^2)
穩(wěn)定性：穩(wěn)定排序算法。
使用場景：適用于小規(guī)模數(shù)據(jù)，也適用于部分有序的大規(guī)模數(shù)據(jù)。
詳細介紹: https://www.runoob.com/w3cnote/insertion-sort.html
視頻講解: https://www.bilibili.com/video/BV1TD4y1Q751

"""
3.插入排序
    遍歷i時 (0, i-1)是有序的 將i插入到(0, i-1)序列中   (i, n)無序的
    找到一個合適的所用在(0, i-1) 中找到一個合適的位置進行插入
    1.在每一輪循環(huán)中，找到未排序部分中的最小元素的索引，然后將最小元素與當前位置進行交換。
    2.每一輪循環(huán)會將一個最小元素放到已排序部分的末尾。
復(fù)雜度: O(n^2)
穩(wěn)定性：穩(wěn)定排序算法。
使用場景：適用于小規(guī)模數(shù)據(jù)，也適用于部分有序的大規(guī)模數(shù)據(jù)。
詳細介紹: https://www.runoob.com/w3cnote/insertion-sort.html
視頻講解: https://www.bilibili.com/video/BV1TD4y1Q751
"""
def insert_sort(arr):
    n = len(arr)
    for i in range(1, n):
        preIndex = i-1
        current = arr[i]
        # 大于current的元素向右移動
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex+1] = current
    print(f"arr: {arr}")
    return current

if __name__ == '__main__':
    arr = [10, 8, 11, 7, 4, 12]
    insert_sort(arr)

4 希爾排序

八大排序算法 (python版本),LeetCode,排序算法,python,算法

圖4摘自博客園

4.希爾排序 (gap為1就是插入排序)
希爾排序的基本思想是
1. 將數(shù)組中相距一定間隔(gap)的元素分成一組，
2. 對每組使用插入排序，然后逐步減小間隔直至為1，最終完成排序。

穩(wěn)定性：不穩(wěn)定排序算法。
使用場景：適用于中等規(guī)模數(shù)據(jù)，對于大規(guī)模數(shù)據(jù)效果也不錯。
復(fù)雜度: 最壞情況下取決于間隔序列，通常介于 O(nlog n)和 O(n^2) 之間。
詳細介紹: https://www.runoob.com/w3cnote/shell-sort.html
視頻講解: https://www.bilibili.com/video/BV1BK4y1478X

"""
4.希爾排序 (gap為1就是插入排序) 
    希爾排序的基本思想是
    1. 將數(shù)組中相距一定間隔(gap)的元素分成一組，
    2. 對每組使用插入排序，然后逐步減小間隔直至為1，最終完成排序。

穩(wěn)定性：不穩(wěn)定排序算法。
使用場景：適用于中等規(guī)模數(shù)據(jù)，對于大規(guī)模數(shù)據(jù)效果也不錯。
復(fù)雜度: 最壞情況下取決于間隔序列，通常介于 O(nlog n)和 O(n^2) 之間。
詳細介紹: https://www.runoob.com/w3cnote/shell-sort.html
視頻講解: https://www.bilibili.com/video/BV1BK4y1478X
"""

def shell_sort(arr):
    n = len(arr)
    gap = n // 3
    while gap > 0:
        for i in range(gap, n):  # 從gap開始因為要從第二個開始插入, 第一個元素已經(jīng)是有序的
            current = arr[i]
            preIndex = i - gap
            while preIndex >= 0 and arr[preIndex] > current:
                arr[preIndex+gap] = arr[preIndex]
                preIndex -= gap
            arr[preIndex+gap] = current
        gap //= 2
    return arr

if __name__ == '__main__':
    # 測試
    arr = [12, 34, 54, 2, 3]
    shell_sort(arr)
    print("排序后的數(shù)組：", arr)

5. 歸并排序

八大排序算法 (python版本),LeetCode,排序算法,python,算法

圖5摘自菜鳥教程

歸并排序算法步驟: (遞歸和棧)
1. 先歸(一致分)
2. 然后并(比較排序)

時間復(fù)雜度：O(nlogn)但需要額外的空間來存儲中間結(jié)果。
穩(wěn)定性：穩(wěn)定排序算法。
使用場景：適用于大規(guī)模數(shù)據(jù)，對數(shù)據(jù)規(guī)模不敏感，效率穩(wěn)定。
復(fù)雜度: O(nlogn)
詳細介紹: https://www.runoob.com/w3cnote/merge-sort.html
視頻講解: https://www.bilibili.com/video/BV1Pt4y197VZ

"""
5. 歸并排序 (遞歸和棧)
    1. 先歸(一致分)
    2. 然后并(比較排序)

時間復(fù)雜度：O(nlogn)但需要額外的空間來存儲中間結(jié)果。
穩(wěn)定性：穩(wěn)定排序算法。
使用場景：適用于大規(guī)模數(shù)據(jù)，對數(shù)據(jù)規(guī)模不敏感，效率穩(wěn)定。
復(fù)雜度: O(nlogn)
詳細介紹: https://www.runoob.com/w3cnote/merge-sort.html
視頻講解: https://www.bilibili.com/video/BV1Pt4y197VZ
"""
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): # left, right都是有序數(shù)組
    i = j = 0
    res_list = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res_list.append(left[i])
            i += 1
        else:
            res_list.append(right[j])
            j += 1
    res_list.extend(left[i:])
    res_list.extend(right[j:])
    return res_list



if __name__ == '__main__':
    # 測試
    arr = [12, 11, 13, 5, 6, 7]
    sorted_arr = merge_sort(arr)
    print("排序后的數(shù)組：", sorted_arr)

6. 快速排序(重點!!!)

八大排序算法 (python版本),LeetCode,排序算法,python,算法

圖6摘自菜鳥教程

算法步驟:

從數(shù)列中挑出一個元素，稱為 “基準”（pivot）;
重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序；

復(fù)雜度: O(nlogn) 最壞情況下 O(n^2) (當選擇的主元極不均勻時)。
穩(wěn)定性：不穩(wěn)定排序算法。
使用場景：適用于大規(guī)模數(shù)據(jù)，且在大多數(shù)情況下效率較高。
詳細介紹: https://www.runoob.com/w3cnote/quick-sort-2.html
視頻講解: https://www.bilibili.com/video/BV1WF41187Bp

6.1 方法1:

"""
6. 快速排序 是一種分治算法，
    它選擇一個基準元素，將數(shù)組分成兩個子數(shù)組，
    分別小于和大于基準元素，
    然后對子數(shù)組進行遞歸排序。
復(fù)雜度: O(nlogn) 最壞情況下 O(n^2) (當選擇的主元極不均勻時)。
穩(wěn)定性：不穩(wěn)定排序算法。
使用場景：適用于大規(guī)模數(shù)據(jù)，且在大多數(shù)情況下效率較高。
詳細介紹: https://www.runoob.com/w3cnote/quick-sort-2.html
視頻講解: https://www.bilibili.com/video/BV1WF41187Bp
"""
def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr)-1]
    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)

if __name__ == '__main__':
    # arr =
    arr = [5, 3, 4, 2, 1]
    sorted_arr = quick_sort(arr)
    print("排序后的數(shù)組：", sorted_arr)

6.2 方法2:

"""
6. 快速排序 是一種分治算法，
    它選擇一個基準元素，將數(shù)組分成兩個子數(shù)組，
    分別小于和大于基準元素，
    然后對子數(shù)組進行遞歸排序。
復(fù)雜度: O(nlogn)
詳細介紹: https://www.runoob.com/w3cnote/quick-sort-2.html
視頻講解: https://www.bilibili.com/video/BV1WF41187Bp
"""


def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index-1)
        quick_sort(arr, pivot_index + 1, high)

# 進行分區(qū)， 返回分區(qū)后pivot的坐標pivotIndex的 左邊都小于等于pivot, 右邊都大于等于pivot
# 退出循環(huán)時 right + 1 = left, arr[right] <= pivot arr[right+1] >= pivot 所以 low 和 right 交換值
def partition(arr, low, high):
    pivot = arr[low]								# 基點
    left = low + 1
    right = high
    flag = False
    #  退出循環(huán)的時候 arr[r]指向的肯定是小于pivot
    while True:
        while left <= right and arr[left] <= pivot:		# 這里不使用等號可能出現(xiàn)死循環(huán) [5, 5] /[5, 6, 5, 1]
            left = left + 1
        while left <= right and arr[right] >= pivot:   # 這里不使用等號可能出現(xiàn)死循環(huán)
            right = right - 1
        if right < left:
            break
        else:
            arr[left], arr[right] = arr[right], arr[left]

    arr[low], arr[right] = arr[right], arr[low]
    return right

# # 示例
# unsorted_list = [3, 6, 8, 10, 1, 2, 1]
# quick_sort(unsorted_list, 0, len(unsorted_list) - 1)
# print(unsorted_list)  # 輸出：[1, 1, 2, 3, 6, 8, 10]

if __name__ == '__main__':
    # arr = [12, 11, 13, 5, 6, 7]
    # sorted_arr = quick_sort(arr)
    # print("排序后的數(shù)組：", sorted_arr)
    nums = [5, 3, 4, 2, 1]
    # nums = [12, 11, 13, 5, 6, 7]
    # nums = [3, 6, 8, 10, 1, 2, 1]
    quick_sort(nums, 0, len(nums)-1)
    print("nums: ", nums)

7. 堆排序

八大排序算法 (python版本),LeetCode,排序算法,python,算法

圖7摘自菜鳥教程

堆排序
1. 維護堆的性質(zhì) 復(fù)雜度O(logn)
  父節(jié)點大于等于左孩子與右孩子，不滿足的話依次和左孩子進行交換
2. 建立大頂堆，倒序依次遍歷父節(jié)點n//2 -1 建立大頂堆
3. 堆排序
  逐個從堆中提取最大值，并將其放置到已排序部分的末尾。
  提取的方式是將根節(jié)點與最后一個節(jié)點交換，然后對根節(jié)點進行堆化。

復(fù)雜度：始終為O(nlogn)，且不需要額外空間。
穩(wěn)定性：不穩(wěn)定排序算法。
使用場景：適用于大規(guī)模數(shù)據(jù)，且對內(nèi)存要求較高，適合外部排序。
詳細介紹: https://www.runoob.com/w3cnote/heap-sort.html
視頻講解: https://www.bilibili.com/video/BV1fp4y1D7cj

"""
7. 堆排序
    1. 維護堆的性質(zhì) 復(fù)雜度O(logn)
    父節(jié)點大于等于左孩子與右孩子， 不滿足的話依次和左孩子進行交換
    2. 維護大頂堆， 倒序依次遍歷父節(jié)點  建立大頂堆
    3. 堆排序
    逐個從堆中提取最大值，并將其放置到已排序部分的末尾。
    提取的方式是將根節(jié)點與最后一個節(jié)點交換，然后對根節(jié)點進行堆化。
    
復(fù)雜度：始終為O(nlogn)，且不需要額外空間。
穩(wěn)定性：不穩(wěn)定排序算法。
使用場景：適用于大規(guī)模數(shù)據(jù)，且對內(nèi)存要求較高，適合外部排序。
詳細介紹: https://www.runoob.com/w3cnote/heap-sort.html
視頻講解: https://www.bilibili.com/video/BV1fp4y1D7cj
"""

def heapify(arr, n, i):     # 1.用來維護堆的性質(zhì)
    """
    :param arr: 存儲堆的數(shù)組
    :param n:   數(shù)組長度
    :param i:   待維護節(jié)點的下標
    :return:
    """
    largest = i         # 初始化最大元素索引為根節(jié)點
    lson = 2 * i + 1    # 左子節(jié)點索引
    rson = 2 * i + 2   # 右子節(jié)點索引

    # 找到左右子節(jié)點中較大的索引
    if lson < n and arr[lson] > arr[largest]:
        largest = lson
    if rson < n and arr[rson] > arr[largest]:
        largest = rson

    # 如果最大值不是根節(jié)點，則交換根節(jié)點與最大值
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # 遞歸對受影響的子樹進行堆化
        heapify(arr, n, largest)

# 堆排序
def heap_sort(arr):
    n = len(arr)

    # 倒序依次遍歷父節(jié)點，通過維護堆的性質(zhì)， 構(gòu)建大頂堆 注意這里n是數(shù)組長度而不是索引
    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]  # 交換根節(jié)點與最后一個節(jié)點
        heapify(arr, i, 0)  # 對剩余的堆進行堆化, 這里傳入的是i, 交換之后已經(jīng)脫離了

if __name__ == '__main__':
    # 示例
    unsorted_list = [12, 11, 13, 5, 6, 7]
    heap_sort(unsorted_list)
    print(unsorted_list)  # 輸出：[5, 6, 7, 11, 12, 13]

8 計數(shù)排序

八大排序算法 (python版本),LeetCode,排序算法,python,算法

圖8摘自菜鳥教程

堆排序
適用場景: 計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
（1）找出待排序的數(shù)組中最大和最小的元素
（2）統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項
（3）對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）
（4）反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1

穩(wěn)定性：穩(wěn)定排序算法。
復(fù)雜度: 最好情況下為O(n+k)，其中 k 表示數(shù)據(jù)范圍。
使用場景：適用于數(shù)據(jù)范圍不大，但是數(shù)據(jù)量較大的情況。
詳細介紹: https://www.runoob.com/w3cnote/counting-sort.html
視頻講解: https://www.bilibili.com/video/BV1KU4y1M7VY

"""
8. 堆排序
    適用場景: 計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
    （1）找出待排序的數(shù)組中最大和最小的元素
	（2）統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項
	（3）對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）
	（4）反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1

穩(wěn)定性：穩(wěn)定排序算法。
復(fù)雜度: 最好情況下為O(n+k)，其中 k 表示數(shù)據(jù)范圍。
使用場景：適用于數(shù)據(jù)范圍不大，但是數(shù)據(jù)量較大的情況。
詳細介紹: https://www.runoob.com/w3cnote/counting-sort.html
視頻講解: https://www.bilibili.com/video/BV1KU4y1M7VY
"""
def countingSort(arr):
    maxValue = float("-inf")
    for element in arr:
        maxValue = max(maxValue, element)

    maxLen = maxValue+1
    countArray = [0] * maxLen
    sortedIndex = 0

    arrLen = len(arr)
    for i in range(arrLen):
        # if not bucket[arr[i]]:
        #     bucket[arr[i]]=0
        countArray[arr[i]] += 1
    print(countArray)
    for j in range(maxLen):
        while countArray[j] > 0:
            arr[sortedIndex] = j
            sortedIndex += 1
            countArray[j] -= 1
    return arr
if __name__ == '__main__':
    # 示例
    unsorted_list = [12, 11, 13, 5, 6, 7]
    countingSort(unsorted_list)
    print(unsorted_list)  # 輸出：[5, 6, 7, 11, 12, 13]

總結(jié)

穩(wěn)定的排序方法有：
冒泡排序、插入排序、歸并排序、計數(shù)排序。

不穩(wěn)定的排序方法有
選擇排序，希爾排序，快速排序，堆排序

對于數(shù)據(jù)量少的情況
通常使用
插入排序或冒泡排序，因為它們的常數(shù)因子較小，適用于小規(guī)模數(shù)據(jù)集。

對于數(shù)據(jù)量較大的情況

歸并排序：適用于大規(guī)模數(shù)據(jù)，效率穩(wěn)定，但需要額外的內(nèi)存空間。
快速排序：適用于大規(guī)模數(shù)據(jù)，平均情況下效率較高，但在最壞情況下可能會退化為 O(n^2)。
堆排序：適用于大規(guī)模數(shù)據(jù)，不需要額外空間，但常數(shù)因子較大，效率稍低于快速排序。

數(shù)據(jù)范圍不大，數(shù)據(jù)量較大的情況

計數(shù)排序適用于數(shù)據(jù)范圍不大，數(shù)據(jù)量較大的情況，但由于它需要額外的數(shù)組存儲計數(shù)信息，所以適用場景相對有限。
在實際應(yīng)用中，根據(jù)數(shù)據(jù)量大小、穩(wěn)定性要求、時間復(fù)雜度等因素綜合考慮，選擇適合的排序方法能夠提高程序的性能。
快速排序經(jīng)?？?，如果只掌握一個排序算法的話，首選快速排序算法文章來源地址http://www.zghlxwxcb.cn/news/detail-677089.html

到了這里，關(guān)于八大排序算法 (python版本)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔相關(guān)法律責任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

【算法】經(jīng)典的八大排序算法
點擊鏈接?可視化排序?動態(tài)演示各個排序算法來加深理解，大致如下原理冒泡排序（Bubble Sort）是一種簡單的排序算法，它通過多次比較和交換相鄰元素的方式，將最大（或最小）的元素逐步冒泡到數(shù)組的一端。每一輪冒泡將會將未排序部分中最大（或最?。┑脑亍案　?/p>
2024年02月11日
瀏覽(27)
八大排序算法--選擇排序（動圖理解）
算法思路每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。 ?選擇排序的步驟： 1首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 2再從剩余未排序元素中繼續(xù)尋找最小（大）元
2024年02月14日
瀏覽(19)
八大排序算法--希爾排序（動圖理解）
目錄希爾排序概念算法思路動畫演示代碼如下復(fù)雜度分析時間復(fù)雜度測試運行結(jié)果 ?完整代碼 ?創(chuàng)作不易，如果本篇博客對您有一定的幫助，大家記得留言+點贊哦。概念希爾排序是插入排序的一種，是對直接插入排序的優(yōu)化。其特點在于分組排序。算法思路希爾排序
2024年02月14日
瀏覽(20)
八大排序算法--冒泡排序（動圖理解）
算法思路冒泡排序的原理是：從左到右，相鄰元素進行比較。每次比較一輪，就會找到序列中最大的一個或最小的一個。這個數(shù)就會從序列的最右邊冒出來。以從小到大排序為例，第一輪比較后，所有數(shù)中最大的那個數(shù)就會浮到最右邊；第二輪比較后，所有數(shù)中第二大的那
2024年02月14日
瀏覽(19)
python 八大排序_python-打基礎(chǔ)-八大排序
## 排序篇 #### 二路歸并排序 - 介紹 - 歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應(yīng)用。歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間
2024年01月17日
瀏覽(19)
【數(shù)據(jù)結(jié)構(gòu)】八大排序之簡單選擇排序算法
?? 個人主頁 :修修修也 ?? 所屬專欄 :數(shù)據(jù)結(jié)構(gòu) ?? 操作環(huán)境 : Visual Studio 2022 目錄一.簡單選擇排序簡介及思路二.簡單選擇排序的代碼實現(xiàn) 三.簡單選擇排序的優(yōu)化四.簡單選擇排序的時間復(fù)雜度分析結(jié)語簡單選擇排序算法(Simple Selection Sort) 是一種簡單直觀的選擇排序算
2024年02月01日
瀏覽(24)
【探索排序算法的奧秘】一文初步詳解八大排序
??作者簡介：M malloc，致力于成為嵌入式大牛的男人 ??專欄簡介：本文收錄于初階數(shù)據(jù)結(jié)構(gòu) ，本專欄主要內(nèi)容講述了初階的數(shù)據(jù)結(jié)構(gòu)，如順序表，鏈表，棧，隊列等等，專為小白打造的文章專欄。 ??相關(guān)專欄推薦：LeetCode刷題集，C語言每日一題。本章我將詳細的講解關(guān)于
2024年02月14日
瀏覽(22)
八大排序算法（C語言版）之插入排序
八大排序算法：超鏈接：插入排序選擇排序交換排序歸并排序非比較排序排序:所謂排序，就是使一串記錄，按照其中的某個或某些的大小，遞增或遞減的排列起來的操作。穩(wěn)定性:假定在待排序的記錄序列中，存在多個具有相同的的記錄，若經(jīng)過排序，這些
2024年02月07日
瀏覽(19)
八大排序算法
是指常用的八種排序算法，它們包括：冒泡排序（Bubble Sort）：通過不斷交換相鄰元素的位置，將最大（或最小）的元素逐漸\\\"冒泡\\\"到最后（或最前）的位置。選擇排序（Selection Sort）：每次從未排序的部分中選擇最小（或最大）的元素，并將其放置在已排序部分的末尾。插
2024年02月08日
瀏覽(10)
【C語言】八大排序算法
如需更詳細步驟可見：冒泡排序冒泡排序(bubble sort)是最基礎(chǔ)的排序算法，它是一種基礎(chǔ)的交換排序。它的原理就像汽水一樣，汽水中常常有許多小氣泡飄到上面。而冒泡排序這種排序算法的每一個元素也可以像小氣泡一樣根據(jù)自身大小一點點地向著數(shù)組一端移動。冒泡排
2024年01月18日
瀏覽(16)

<object id="hxvmc"><abbr id="hxvmc"></abbr></object>