Algorithm-Sort

Algorithm-Sort

排序算法总结

---

1.冒泡排序

时间复杂度$O(N^2)$ 空间复杂度$O(1)$

# 数组后面的数为排好序的数，一直交换直到把当前最大的数交换到最后
def bubble_sort(nums):
    n = len(nums)
    for i in range(n):
      for j in range(0:n-1-i):
        if nums[j] > nums[j+1]:
          # 交换
          nums[j],num[j+1] = nums[j+1],nums[j]
    return nums

2.选择排序

3.插入排序

时间复杂度$O(N^2)$ 空间复杂度$O(1)$

# 数组前面的数为排好序的，每次在前面不断交换直到找到当前数的位置
def insertion_sort(nums):
    n = len(nums)
    for i in range(1, n):
        j = i
        while j > 0 and nums[j - 1] > nums[j]:
            nums[j], nums[j - 1] = nums[j - 1], nums[j]
            j -= 1
    return nums

4.希尔排序

5.归并排序

6.快速排序

下面的实现使用额外的数组来存储分区结果，因此空间复杂度除了递归调用栈的空间外，还包括分区数组的空间:

空间复杂度为 O(n)（额外数组）+ O(log n)（递归调用栈）= O(n)。

时间复杂度为 O(log n) （分区操作树的高度）* O(n)（每层的分区操作）= O(nlog n)

def quick_sort(nums):
    # 实现快排
    if len(nums) <= 1:
        return nums
    # 选取基准数
    pivot = nums[len(nums)//2]
    # 实现分区
    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    # 将左右半区递归进行排序
    return quick_sort(left) + middle + quick_sort(right)

使用原地分区的快速排序实现，避免了使用额外的数组，从而优化了空间复杂度：

空间复杂度为 O(log n)（递归调用栈）。

时间复杂度为 O(log n) （分区操作树的高度）* O(n)（每层的分区操作）= O(nlog n)

def quick_sort(nums, low, high):
  if low < high:
    pi = partition(nums, low, high)
    # 递归实现左右分区快排
    quick_sort(nums, low, pi-1)
    quick_sort(nums, pi+1, high)

def partition(nums, low, high):
  # 选取基准数
  pivot = nums[high]
  i = low
  for j in range(low,high):
    if nums[j] < pivot:
      nums[i],nums[j] = nums[j],nums[i]
      i += 1
  nums[i],nums[high] = nums[high],nums[i]
  return i

7.堆排序

堆排序的主要思想是将数组转化为一个大顶堆，然后通过不断将堆顶（最大值）与未排序部分的最后一个元素交换并重新调整堆来实现排序。

从小到大排序，建立大根堆；从大到小排序，建立小根堆。

大根堆：每个结点的值都大于等于其孩子结点的值；小根堆：每个结点的值都小于等于其孩子结点的值。

排序过程：

1.构建大顶堆：将数组转化为一个大顶堆。

2.交换堆顶元素和末尾元素：将堆顶（最大元素）与未排序部分的最后一个元素交换，并缩小堆的范围。

3.调整堆：调整交换后的堆，使其重新成为大顶堆。

4.重复步骤2和步骤3，直到堆的范围缩小到1。

def heapify(arr, h_size, h_index):
  	"""
    调整堆，使其满足大顶堆的性质
    :param arr: 数组
    :param h_size: 堆的大小
    :param h_index: 要调整的节点索引
    """
    # 左右结点的索引值
    left = 2*(h_index) + 1
    right = 2*(h_index) + 2
    # 先设置最大值为当前结点值
    maxIndex = h_index
    # 判断左右结点值是否大于它，进行交换调整
    if left < h_size and arr[left] > arr[maxIndex]:
        maxIndex = left
    if right < h_size and arr[right] > arr[maxIndex]:
        maxIndex = right
    if maxIndex != h_index:
        arr[h_index], arr[maxIndex] = arr[maxIndex], arr[h_index]
        # 递归调整被交换的子树
        heapify(arr, h_size, maxIndex)
        
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)

使用迭代方法来避免递归调用栈，使其空间复杂度保持$O(1)$，迭代方法并不会造成时间复杂度的增加，是因为迭代深度还是类似于堆的高度，所以为$O(\log n)$：

def heapify(arr, n, i):
    while True:
        largest = i  # 初始化最大值为当前节点
        left = 2 * i + 1  # 左子节点
        right = 2 * i + 2  # 右子节点

        # 如果左子节点存在且大于当前最大值，则更新最大值为左子节点
        if left < n and arr[left] > arr[largest]:
            largest = left
        # 如果右子节点存在且大于当前最大值，则更新最大值为右子节点
        if right < n and arr[right] > arr[largest]:
            largest = right
        # 如果最大值不是当前节点，则交换并继续调整子树
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            i = largest
        else:
            break

curl -X DELETE -H “Authorization: token {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@github}” https://api.github.com/repos/Adzuiki23/Super-mario-bros-PPO-pytorch