八大排序算法 (python版本)-Toy模板网

这篇具有很好参考价值的文章主要介绍了八大排序算法 (python版本)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

八大排序算法

个人学习笔记 如有问题欢迎指正交流

快速排序经常考，如果只掌握一个排序算法的话，首选快速排序算法
八大排序算法通常指的是以下八种经典排序算法：

1. 冒泡排序 (Bubble Sort)

使用场景：适用于小规模数据的排序，不推荐用于大规模数据排序。
稳定性：稳定排序算法。
时间复杂度：平均和最坏情况下 O(n^2)，最好情况下 O(n)（当输入数据已经有序时）。

2. 选择排序 (Selection Sort):

使用场景：适用于小规模数据的排序，与冒泡排序类似，不适用于大规模数据排序。
稳定性：不稳定排序算法。
时间复杂度：都为 O(n^2)。

3. 插入排序 (Insertion Sort):

使用场景：适用于小规模数据，也适用于部分有序的大规模数据。
稳定性：稳定排序算法。
时间复杂度：平均和最坏情况下 O(n^2)，最好情况下 O(n)（当输入数据已经有序时）。

4. 希尔排序 (Shell Sort):

使用场景：适用于中等规模数据，对于大规模数据效果也不错。
稳定性：不稳定排序算法。
时间复杂度：最坏情况下取决于间隔序列，通常介于 O(n log n) 和 O(n^2) 之间。

5. 归并排序 (Merge Sort):

使用场景：适用于大规模数据，对数据规模不敏感，效率稳定。
稳定性：稳定排序算法。
时间复杂度：始终为 O(n log n)，但需要额外的空间来存储中间结果。

6. 快速排序 (Quick Sort):

使用场景：适用于大规模数据，且在大多数情况下效率较高。
稳定性：不稳定排序算法。
时间复杂度：平均情况下 O(n log n)，最坏情况下 O(n^2)（当选择的主元极不均匀时）。

7. 堆排序 (Heap Sort):

使用场景：适用于大规模数据，且对内存要求较高，适合外部排序。
稳定性：不稳定排序算法。
时间复杂度：始终为 O(n log n)，且不需要额外空间。

8. 计数排序 (Counting Sort):

使用场景：适用于数据范围不大，但是数据量较大的情况。
稳定性：稳定排序算法。
时间复杂度：最好情况下为 O(n + k)，其中 k 表示数据范围。

每种排序算法都有其独特的应用场景和特点，根据实际问题选择合适的排序算法能够有效提高程序的效率。

1. 冒泡排序

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

图1摘自菜鸟教程

冒泡排序(相邻比较冒泡) 遍历i时 (0, n-i)进行比较 (n-i, n)是有序的
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  针对所有的元素重复以上的步骤，除了最后一个。

复杂度: O(n^2)
稳定性：稳定排序算法。
使用场景：适用于小规模数据的排序，不推荐用于大规模数据排序。
详细介绍: https://www.runoob.com/w3cnote/bubble-sort.html
视频讲解: https://www.bilibili.com/video/BV1Hg4y1q7tz

"""
1.冒泡排序(相邻比较冒泡) 遍历i次之后 (0, n-i)进行比较 (n-i, n)是有序的
    1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
    2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
    针对所有的元素重复以上的步骤，除了最后一个。
复杂度: O(n^2)
稳定性：稳定排序算法。
使用场景：适用于小规模数据的排序，不推荐用于大规模数据排序。
详细介绍: 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. 在每一轮循环中，找到未排序部分中的最小元素的索引，然后将最小元素与当前位置进行交换。
2. 每一轮循环会将一个最小元素放到已排序部分的末尾。

复杂度: O(n^2)
稳定性：不稳定排序算法。
使用场景：适用于小规模数据的排序，与冒泡排序类似，不适用于大规模数据排序。
详细介绍: https://www.runoob.com/w3cnote/selection-sort.html
视频讲解: https://www.bilibili.com/video/BV1VK4y1475t

"""
2.选择排序 遍历i次之后 操作(0, i)是有序的 (i, n) 进行比较
    (选择最小(最大)的在未排序的最开始(末尾)位置) 针对(i, n)进行的排序
    1.在每一轮循环中，找到未排序部分中的最小元素的索引，然后将最小元素与当前位置进行交换。
    2.每一轮循环会将一个最小元素放到已排序部分的末尾。
复杂度: O(n^2)
稳定性：不稳定排序算法。
使用场景：适用于小规模数据的排序，与冒泡排序类似，不适用于大规模数据排序。
详细介绍: 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. 在每一轮循环中，找到未排序部分中的最小元素的索引，然后将最小元素与当前位置进行交换。
2. 每一轮循环会将一个最小元素放到已排序部分的末尾。

复杂度: O(n^2)
稳定性：稳定排序算法。
使用场景：适用于小规模数据，也适用于部分有序的大规模数据。
详细介绍: 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.在每一轮循环中，找到未排序部分中的最小元素的索引，然后将最小元素与当前位置进行交换。
    2.每一轮循环会将一个最小元素放到已排序部分的末尾。
复杂度: O(n^2)
稳定性：稳定排序算法。
使用场景：适用于小规模数据，也适用于部分有序的大规模数据。
详细介绍: 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. 将数组中相距一定间隔(gap)的元素分成一组，
2. 对每组使用插入排序，然后逐步减小间隔直至为1，最终完成排序。

稳定性：不稳定排序算法。
使用场景：适用于中等规模数据，对于大规模数据效果也不错。
复杂度: 最坏情况下取决于间隔序列，通常介于 O(nlog n)和 O(n^2) 之间。
详细介绍: https://www.runoob.com/w3cnote/shell-sort.html
视频讲解: https://www.bilibili.com/video/BV1BK4y1478X

"""
4.希尔排序 (gap为1就是插入排序) 
    希尔排序的基本思想是
    1. 将数组中相距一定间隔(gap)的元素分成一组，
    2. 对每组使用插入排序，然后逐步减小间隔直至为1，最终完成排序。

稳定性：不稳定排序算法。
使用场景：适用于中等规模数据，对于大规模数据效果也不错。
复杂度: 最坏情况下取决于间隔序列，通常介于 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开始因为要从第二个开始插入, 第一个元素已经是有序的
            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("排序后的数组：", arr)

5. 归并排序

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

图5摘自菜鸟教程

归并排序算法步骤: (递归和栈)
1. 先归(一致分)
2. 然后并(比较排序)

时间复杂度：O(nlogn)但需要额外的空间来存储中间结果。
稳定性：稳定排序算法。
使用场景：适用于大规模数据，对数据规模不敏感，效率稳定。
复杂度: O(nlogn)
详细介绍: https://www.runoob.com/w3cnote/merge-sort.html
视频讲解: https://www.bilibili.com/video/BV1Pt4y197VZ

"""
5. 归并排序 (递归和栈)
    1. 先归(一致分)
    2. 然后并(比较排序)

时间复杂度：O(nlogn)但需要额外的空间来存储中间结果。
稳定性：稳定排序算法。
使用场景：适用于大规模数据，对数据规模不敏感，效率稳定。
复杂度: 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都是有序数组
    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("排序后的数组：", sorted_arr)

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

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

图6摘自菜鸟教程

算法步骤:

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

复杂度: O(nlogn) 最坏情况下 O(n^2) (当选择的主元极不均匀时)。
稳定性：不稳定排序算法。
使用场景：适用于大规模数据，且在大多数情况下效率较高。
详细介绍: https://www.runoob.com/w3cnote/quick-sort-2.html
视频讲解: https://www.bilibili.com/video/BV1WF41187Bp

6.1 方法1:

"""
6. 快速排序 是一种分治算法，
    它选择一个基准元素，将数组分成两个子数组，
    分别小于和大于基准元素，
    然后对子数组进行递归排序。
复杂度: O(nlogn) 最坏情况下 O(n^2) (当选择的主元极不均匀时)。
稳定性：不稳定排序算法。
使用场景：适用于大规模数据，且在大多数情况下效率较高。
详细介绍: 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("排序后的数组：", sorted_arr)

6.2 方法2:

"""
6. 快速排序 是一种分治算法，
    它选择一个基准元素，将数组分成两个子数组，
    分别小于和大于基准元素，
    然后对子数组进行递归排序。
复杂度: 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)

# 进行分区， 返回分区后pivot的坐标pivotIndex的 左边都小于等于pivot, 右边都大于等于pivot
# 退出循环时 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
    #  退出循环的时候 arr[r]指向的肯定是小于pivot
    while True:
        while left <= right and arr[left] <= pivot:		# 这里不使用等号可能出现死循环 [5, 5] /[5, 6, 5, 1]
            left = left + 1
        while left <= right and arr[right] >= pivot:   # 这里不使用等号可能出现死循环
            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("排序后的数组：", 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. 维护堆的性质复杂度O(logn)
  父节点大于等于左孩子与右孩子，不满足的话依次和左孩子进行交换
2. 建立大顶堆，倒序依次遍历父节点n//2 -1 建立大顶堆
3. 堆排序
  逐个从堆中提取最大值，并将其放置到已排序部分的末尾。
  提取的方式是将根节点与最后一个节点交换，然后对根节点进行堆化。

复杂度：始终为O(nlogn)，且不需要额外空间。
稳定性：不稳定排序算法。
使用场景：适用于大规模数据，且对内存要求较高，适合外部排序。
详细介绍: https://www.runoob.com/w3cnote/heap-sort.html
视频讲解: https://www.bilibili.com/video/BV1fp4y1D7cj

"""
7. 堆排序
    1. 维护堆的性质 复杂度O(logn)
    父节点大于等于左孩子与右孩子， 不满足的话依次和左孩子进行交换
    2. 维护大顶堆， 倒序依次遍历父节点  建立大顶堆
    3. 堆排序
    逐个从堆中提取最大值，并将其放置到已排序部分的末尾。
    提取的方式是将根节点与最后一个节点交换，然后对根节点进行堆化。
    
复杂度：始终为O(nlogn)，且不需要额外空间。
稳定性：不稳定排序算法。
使用场景：适用于大规模数据，且对内存要求较高，适合外部排序。
详细介绍: https://www.runoob.com/w3cnote/heap-sort.html
视频讲解: https://www.bilibili.com/video/BV1fp4y1D7cj
"""

def heapify(arr, n, i):     # 1.用来维护堆的性质
    """
    :param arr: 存储堆的数组
    :param n:   数组长度
    :param i:   待维护节点的下标
    :return:
    """
    largest = i         # 初始化最大元素索引为根节点
    lson = 2 * i + 1    # 左子节点索引
    rson = 2 * i + 2   # 右子节点索引

    # 找到左右子节点中较大的索引
    if lson < n and arr[lson] > arr[largest]:
        largest = lson
    if rson < n and arr[rson] > arr[largest]:
        largest = rson

    # 如果最大值不是根节点，则交换根节点与最大值
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # 递归对受影响的子树进行堆化
        heapify(arr, n, largest)

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

    # 倒序依次遍历父节点，通过维护堆的性质， 构建大顶堆 注意这里n是数组长度而不是索引
    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)  # 对剩余的堆进行堆化, 这里传入的是i, 交换之后已经脱离了

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 计数排序

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

图8摘自菜鸟教程

堆排序
适用场景: 计数排序要求输入的数据必须是有确定范围的整数。
（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

稳定性：稳定排序算法。
复杂度: 最好情况下为O(n+k)，其中 k 表示数据范围。
使用场景：适用于数据范围不大，但是数据量较大的情况。
详细介绍: https://www.runoob.com/w3cnote/counting-sort.html
视频讲解: https://www.bilibili.com/video/BV1KU4y1M7VY

"""
8. 堆排序
    适用场景: 计数排序要求输入的数据必须是有确定范围的整数。
    （1）找出待排序的数组中最大和最小的元素
	（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
	（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
	（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

稳定性：稳定排序算法。
复杂度: 最好情况下为O(n+k)，其中 k 表示数据范围。
使用场景：适用于数据范围不大，但是数据量较大的情况。
详细介绍: 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]

总结

稳定的排序方法有：
冒泡排序、插入排序、归并排序、计数排序。

不稳定的排序方法有
选择排序，希尔排序，快速排序，堆排序

对于数据量少的情况
通常使用
插入排序或冒泡排序，因为它们的常数因子较小，适用于小规模数据集。

对于数据量较大的情况

归并排序：适用于大规模数据，效率稳定，但需要额外的内存空间。
快速排序：适用于大规模数据，平均情况下效率较高，但在最坏情况下可能会退化为 O(n^2)。
堆排序：适用于大规模数据，不需要额外空间，但常数因子较大，效率稍低于快速排序。

数据范围不大，数据量较大的情况

计数排序适用于数据范围不大，数据量较大的情况，但由于它需要额外的数组存储计数信息，所以适用场景相对有限。
在实际应用中，根据数据量大小、稳定性要求、时间复杂度等因素综合考虑，选择适合的排序方法能够提高程序的性能。
快速排序经常考，如果只掌握一个排序算法的话，首选快速排序算法文章来源地址https://www.toymoban.com/news/detail-677089.html

到了这里，关于八大排序算法 (python版本)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！