1、冒泡排序

👆^{_{点击标题看算法介绍}}

时间复杂度最好为O(n)，最坏为O(n²)，其中n是要排序的元素个数
空间复杂度为O(1)，因为它只需要固定的额外空间来进行元素交换，与待排序数据量无关。

def bubbleSort(arr):
    for i in range(len(arr) - 1):  # 来回推len(arr)-1次 i就是已经排序完成了多少到最后
        for j in range(len(arr) - i - 1):  # 每一遍都会把未排序部分中最大的推到后面 橙色已排序的部分不需要再排了 故-i
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 大的往后排 置换数值
    return arr

if __name__ == '__main__':
    arr_li = [1, 3, 9, 4, 0, 2, 7, 5, 8, 6]
    print(bubbleSort(arr_li))

2、选择排序

选择排序的时间复杂度为O(n²)，空间复杂度为O(1)。

def selectionSort(arr):
    for i in range(len(arr) - 1):
        minInd = i  # 放置最小值的下标
        for j in range(i + 1, len(arr)):  # 跳过已经排序好的前i个 每次都到len(arr)最后一个元素
            print(j)
            if arr[j] < arr[minInd]:
                minInd = j
        # 每一次大遍历后 对比剩余部分最小值和遍历起始下标值
        if minInd != i:
            arr[i], arr[minInd] = arr[minInd], arr[i]
    return arr

if __name__ == '__main__':
    arr_li = [1, 3, 9, 4, 0, 2, 7, 5, 8, 6]
    print(selectionSort(arr_li))

3、插入排序

同冒泡排序时空复杂度，时间复杂度为最好为O(n)，最坏为O(n²)，，空间复杂度为O(1)。

def insertionSort(arr):
    for i in range(len(arr)):  # 大遍历次数len(arr)
        current = arr[i]  # 每次拿出一个current数组  依次和前面的作比较
        preInd = i - 1  # current要和这个下标的值对比 第一次是和下标-1的对比 即直接将current放在preInd前(作为排序好的首位)
        while preInd >= 0 and arr[preInd] > current:
            arr[preInd + 1] = arr[preInd]
            preInd -= 1  # 继续往前对比
        arr[preInd + 1] = current  # 直到前面没有比current大的了 将current放进刚对比的arr[preInd]前
    return arr

if __name__ == '__main__':
    arr_li = [1, 3, 9, 4, 0, 2, 7, 5, 8, 6]
    print(insertionSort(arr_li))

4、希尔排序

时间复杂度取决于增量序列的选择，在O(n log₂ n)与O(n²)之间。
空间复杂度为O(1)，因为希尔排序在排序过程中只需要常数级别的额外空间来存储临时变量。

希尔动画1

希尔动画2

def shellSort(arr):
    gap = len(arr) // 2
    while gap > 0:  # 每一次跳gap次取元素作为一组
        for i in range(gap, len(arr)):  # 对同一组内的元素进行插入排序 从后往前遍历已排序的元素并插入 56789
            tempInd = i
            while tempInd >= gap and arr[tempInd] < arr[tempInd - gap]:
                arr[tempInd], arr[tempInd - gap] = arr[tempInd - gap], arr[tempInd]
                tempInd -= gap
        gap //= 2
    return arr

if __name__ == '__main__':
    arr_li = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    print(shellSort(arr_li))

5、归并排序

归并排序的时间复杂度是O(n log_e n)，其中n是要排序的元素数量。
空间复杂度是O(n)，因为归并排序需要额外的内存空间来存储临时的合并结果。

def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    L, R = arr[:mid], arr[mid:]  # 二路
    mergeSort(L)  # 同L=mergeSort(L)
    mergeSort(R)
    i = j = k = 0  # i为L的下标 j为R的下标 k为结果arr的下标
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    arr[k:] = L[i:] if i < len(L) else R[j:]  # 如果L或R有剩余部分 将全部追加至尾部
    return arr

if __name__ == '__main__':
    arr_li = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    print(mergeSort(arr_li))

6、快速排序

时间复杂度最好为O(n log_e n)、最坏为O(n²)。空间复杂度为O(log_e n)。

def quicklySort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]  # 每次都拿arr中第一个
        less_than_pivot = [x for x in arr[1:] if x <= pivot]  # 遍历出所有比第一个要小等于的
        greater_than_pivot = [x for x in arr[1:] if x > pivot]  # 遍历出所有比第一个要大的
        return quicklySort(less_than_pivot) + [pivot] + quicklySort(greater_than_pivot)  # 小的继续递归 + 中值(第一个元素) + 大的继续递归

if __name__ == '__main__':
    arr_li = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    print(quicklySort(arr_li))

7、堆排序

堆排序的时间复杂度为 O(n log_e n)，其中 n 是要排序的元素数量。
由于堆排序是原地排序算法，所以它的空间复杂度为 O(1)，即它不需要额外的辅助空间来进行排序。

def heapify(arr, n, i):
    """
    对以i为根节点的子树进行堆调整
    """
    largest = i
    l, r = 2 * i + 1, 2 * i + 2  # 左右子节点
    if l < n and arr[l] > arr[largest]:  # 找出左右子节点和根节点中的最大值
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:  # 如果根节点不是最大值，交换根节点和最大值节点的值，并递归调整子树
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(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

if __name__ == '__main__':
    arr_li = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    print(heapSort(arr_li))

8、计数排序

计数排序的时间复杂度和空间复杂度均为 O(n+k)，其中 n 是输入数组的大小，k 是输入的整数的范围（最大值减最小值加1）。

def countingSort(arr):
    return [x for x in range(max(arr)+1) for _ in range(arr.count(x))]

if __name__ == '__main__':
    arr_li = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    print(countingSort(arr_li))

9、桶排序

桶排序的时间复杂度取决于桶的数量和每个桶内部排序所使用的算法。
时间复杂度最好为O(n+k)，最坏为O(n²)。空间复杂度为O(n+k)，其中n是待排序元素的个数，k是桶的数量。

def bucketSort(arr):
    # 创建空桶列表
    buckets = [0] * (max(arr) + 1)
    # 将元素放入对应的桶中
    for num in arr:
        buckets[num] += 1
    # 合并排序好的桶中的元素
    sorted_arr = []
    for i in range(len(buckets)):
        sorted_arr.extend([i] * buckets[i])
    return sorted_arr

if __name__ == '__main__':
    arr_li = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    print(bucketSort(arr_li))

10、基数排序

时间复杂度为O(nk)，空间复杂度为O(n+k)，其中n是数组中元素的个数，k是数字的最大值。

# 利用以下的计数排序
def countingSort(arr, exp):
    return [x for x in range(10) for _ in range(arr.count(x // exp % 10))]
# 进行基数排序
def radixSort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        arr = countingSort(arr, exp)
        exp *= 10
    return arr

if __name__ == '__main__':
    arr_li = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    print(radixSort(arr_li))

完整代码

# 冒泡排序
def bubbleSort(arr):
    for i in range(len(arr) - 1):  # 来回推len(arr)-1次 i就是已经排序完成了多少到最后
        for j in range(len(arr) - i - 1):  # 每一遍遍历都会把未排序部分中最大的推到后面 对后已排序的部分不需要再排了 所以是len(arr)-i
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 大的往后排 置换数值
    return arr


# 选择排序
def selectionSort(arr):
    for i in range(len(arr) - 1):
        minInd = i  # 放置最小值的下标
        for j in range(i + 1, len(arr)):  # 跳过已经排序好的前i个 每次都到len(arr)最后一个元素
            if arr[j] < arr[minInd]:
                minInd = j
        # 每一次大遍历后 对比剩余部分最小值和遍历起始下标值
        if minInd != i:
            arr[i], arr[minInd] = arr[minInd], arr[i]
    return arr


# 插入排序
def insertionSort(arr):
    for i in range(len(arr)):  # 大遍历次数len(arr)
        current = arr[i]  # 每次拿出一个current数组  依次和前面的作比较
        preInd = i - 1  # current要和这个下标的值对比 第一次是和下标-1的对比 即直接将current放在preInd前(作为排序好的首位)
        while preInd >= 0 and arr[preInd] > current:
            arr[preInd + 1] = arr[preInd]
            preInd -= 1  # 继续往前对比
        arr[preInd + 1] = current  # 直到前面没有比current大的了 将current放进刚对比的arr[preInd]前
    return arr


# 希尔排序
def shellSort(arr):
    gap = len(arr) // 2
    while gap > 0:  # 每一次跳gap次取元素作为一组
        for i in range(gap, len(arr)):  # 对同一组内的元素进行插入排序 从后往前遍历已排序的元素并插入 56789
            tempInd = i
            while tempInd >= gap and arr[tempInd] < arr[tempInd - gap]:
                arr[tempInd], arr[tempInd - gap] = arr[tempInd - gap], arr[tempInd]
                tempInd -= gap
        gap //= 2
    return arr


# (二路)归并排序
def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    L, R = arr[:mid], arr[mid:]  # 二路
    mergeSort(L)  # 同L=mergeSort(L)
    mergeSort(R)
    i = j = k = 0  # i为L的下标 j为R的下标 k为结果arr的下标
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    arr[k:] = L[i:] if i < len(L) else R[j:]  # 如果L或R有剩余部分 将全部追加至尾部
    return arr


# 快速排序
def quicklySort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]  # 每次都拿arr中第一个
        less_than_pivot = [x for x in arr[1:] if x <= pivot]  # 遍历出所有比第一个要小等于的
        greater_than_pivot = [x for x in arr[1:] if x > pivot]  # 遍历出所有比第一个要大的
        return quicklySort(less_than_pivot) + [pivot] + quicklySort(greater_than_pivot)  # 小的继续递归 + 中值(第一个元素) + 大的继续递归


# 堆排序-堆节点遍历
def heapify(arr, n, i):
    """
    对以i为根节点的子树进行堆调整
    """
    largest = i
    l, r = 2 * i + 1, 2 * i + 2  # 左右子节点
    if l < n and arr[l] > arr[largest]:  # 找出左右子节点和根节点中的最大值
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:  # 如果根节点不是最大值，交换根节点和最大值节点的值，并递归调整子树
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


# 堆排序
def heapSort(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


# 计数排序
def countingSort(arr):
    return [x for x in range(max(arr) + 1) for _ in range(arr.count(x))]


# 桶排序
def bucketSort(arr):
    # 创建空桶列表
    buckets = [0] * (max(arr) + 1)

    # 将元素放入对应的桶中
    for num in arr:
        buckets[num] += 1

    # 合并排序好的桶中的元素
    sorted_arr = []
    for i in range(len(buckets)):
        sorted_arr.extend([i] * buckets[i])

    return sorted_arr


# 基数排序-内嵌计数排序
def countingSort(arr, exp):
    return [x for x in range(10) for _ in range(arr.count(x // exp % 10))]


# 基数排序
def radixSort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        arr = countingSort(arr, exp)
        exp *= 10
    return arr


if __name__ == '__main__':
    arr_li = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    print(radixSort(arr_li))

版权声明 1 本网站名称：第一站
2 本站永久网址：https://jinke.love
3 本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系管理员微信: Zhang-jk_1999 进行删除处理。
4 本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5 本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6 本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。
7 本站所有源码都可搭建成功，如需帮搭建部署，需要另付费用。
8 本站资源一经售出不退不换，资源收费仅为平台服务器续费，感谢支持。

THE END

算法

评论共2条

欢迎您留下宝贵的见解！

提交

只看作者

- alex2
  老铁666
  2个月前北京回复
- Alexa8811
  The Beatles - легендарная британская рок-группа, сформированная в 1960 году в Ливерпуле. Их музыка стала символом эпохи и оказала огромное влияние на мировую культуру. Среди их лучших песен: "Hey Jude", "Let It Be", "Yesterday", "Come Together", "Here Comes the Sun", "A Day in the Life", "Something", "Eleanor Rigby" и многие другие. Их творчество отличается мелодичностью, глубиной текстов и экспериментами в звуке, что сделало их одной из самых влиятельных групп в истории музыки. Музыка 2024 года слушать онлайн и скачать бесплатно mp3.
  2个月前加拿大回复

经典排序算法-Python篇