常用排序算法

更多算法：https://book.zbmain.com/question/ALG/

哈希排序：O(N) O(1)

• 基本思想：利用桶概念哈希排序，将数组中的值映射到有限的O(1)数值表中.类型：TF-IDF
• 前提：桶的个数必须大于排序数组中最大值，可以自定义，也可以用max()获取
• 过程：
  • 生成一个有限的数值映射数组
  • 遍历排序数组，将其在映射数组中的频次+1
  • 遍历映射数组，将所有位置的数值放入原数组中（为了不增加空间复杂度），放入次数=频次
• 说明：
  • 传说中的时间复杂度O(N)排序。因为桶被当成了常量，严格可以看作：O（N+MAX）
  • 空间复杂度O(1)。因为映射表长度也被看作常量，严格可以看作：O(MAX)
• 代码：

  from typing import List
      # 长度必须大于数组中最大值
      MAX = 65535
      def hash_sort(nums:List[int]):
          MAX = max(nums)+1
          lst = MAX * [0]
          for i in nums:
              lst[i] += 1
          index = 0
          for i in enumerate(lst):
              for j in range(i[1]):
                  nums[index] = i[0]
                  index += 1
          return nums

  桶排序：O(N+K) O(n*k)

• 基本思想：构建N个桶,将数组中放置到各区间的桶内，进行小范围排序后依次取出。
• 过程：
  • 构建N各桶，N = (MAX-MIN)/len
  • 遍历数组，数组中的数置于各区间桶中
  • 小桶排序
  • 取出数，合并（此处使用了sum()高级用法）
• 说明：因为此处的sorted是O(NlogN)，但是它是经过分类后的小范围快排，故在比较上忽略掉了。
• 代码：

  def bucket_sort(arr): 
    max_,min_=max(arr),min(arr)
    stride=(max_-min_)/len(arr)
    buckets=[[] for i in range(len(arr)+1)]
    for num in arr:
        buckets[int((num-min_)//stride)].append(num)
    arr = [sorted(bucket) for bucket in buckets]
    return sum(arr,[])# sum高级用法，加和从[]开始（二维数组中[]开始）
  
  print(bucket_sort([54,26,93,21,17,77,31,44,55,20]))

快速排序：O(NlogN) O(logN)

• 基本思想: 选出一个数，不断切分成大、小数组。
• 过程:
  • 从数组中取出一个数：key
  • 将比key小的置左，将比key大的置后
  • 对左右两个小数组重复步骤二，直到小数组无法再分
• 复杂度：时间O(NlogN) 空间O(logN)
• 代码:

  # 快排写法
  def quicksort(arr, low, high):
      if low < high:
          pivot = partition(arr, low, high)
          quicksort(arr, low, pivot - 1)
          quicksort(arr, pivot + 1, high)
  def partition(arr, low, high):
      i = low - 1  # 索引
      pivot = arr[high]  # 基准
      for j in range(low, high):
          if arr[j] <= pivot:
              i += 1
              arr[i], arr[j] = arr[j], arr[i]
      arr[i + 1], arr[high] = arr[high], arr[i + 1]
      return (i + 1)
  
  # 精简写法
  def quick_sort(arr: List[int]):
      if len(arr) < 2:
          return arr
      l = [n for n in arr[1:] if n < arr[0]]
      r = [n for n in arr[1:] if n > arr[0]]
      return quick_sort(l) + [arr[0]] + quick_sort(r)
  
  # lambda一行写法
  q_sort = lambda x: [] if len(x) == 0 else \
      q_sort([s for s in x[1:] if s < x[0]]) \
      + [x[0]] + \
      q_sort([s for s in x[1:] if s > x[0]])

插入排序：O(N²) O(1)

• 基本思想：构建有序序列，将未排序的数据，在已排序的序列中从后向前扫描，插入到相应位置。
• 过程：
  • 假设第一个数位置已排序好
  • 从第二个数开始与前面的比较，小数前移，不断优化前置的顺序数列
• 复杂度：时间O(N²) 空间O(1)
• 代码：

   # 插入
  def insertionSort(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
      return arr

  冒泡排序：O(N²) O(1)

• 基本思想：比较相邻两个数的大小，较大的下沉，较小的前置
• 过程：
  • 比较两个数，若后面的数小，交换位置（小数前置/大数后置）
  • 两两比较，一直到比较最前的两个数。最终最小的数交换到起始位置
  • 重复执行，将2、3…n-1个最小数排列成功。
• 优化：设置一个状态，若某轮检索，没有交换任何元素，说明已经排好，直接停止。
• 复杂度：时间O(N²) 空间O(1)
• 代码：

  def bouble_sort(arr: List[int]):
      l = len(arr) - 1
      flag = True  # 优化点
      i = j = 0
      while i < l:
          j = 0
          while j < l - i:
              if arr[j] > arr[j + 1]:
                  arr[j], arr[j + 1] = arr[j + 1], arr[j]
                  flag = False
              j += 1
          if flag:
              break
          i += 1
      return arr

堆排序：O(NlogN) O(1)

• 基本思想：利用堆积构建完全二叉树。
• 过程：（具体步骤需要深入理解）
  • 将列表堆化（完全二叉树）父节点值 > 左右节点值
  • 交换头尾元素后，摘出最大值，破坏堆积后重新进行堆化
  • 依次交换优化堆积后，列表排序成功
• 复杂度：时间O(NlogN) 空间O(1)
• 代码：

  # 堆排序
  def heap_sort(tree: List[int]):
      n = len(tree)
      # 根据列表，反向构建完全二叉树的堆积
      for i in range(n, -1, -1):
          heapify(tree, n, i)
      # 依次交换尾、头元素，交换导致破坏堆结构后，再次优化堆积
      for i in range(n - 1, 0, -1):
          tree[i], tree[0] = tree[0], tree[i]
          heapify(tree, i, 0)
      return tree
  
  # 堆化
  def heapify(tree: List[int], n, i):
      if i >= n:
          return
      # 列表堆化的三角节点与索引关系：i父节点p=(i-1)/2 左孩子l=2i+1 右孩子r=2i+2
      l = 2 * i + 1
      r = 2 * i + 2
      max = i	# 设法找到最大值
      if l < n and tree[l] > tree[i]:
          max = l
      if r < n and tree[r] > tree[max]:
          max = r
      if max != i: # 找到max后，若max不是原父节点i，交换一下，重新堆化
          tree[i], tree[max] = tree[max], tree[i]
          heapify(tree, n, max)

  两个数组相对排序

  from typing import List
  class Solution:
      # 方法一 sort(key)
      def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:        
          ranks = {x: i for i, x in enumerate(arr2)}
          arr1.sort(key=lambda x:(0,ranks[x]) if x in ranks else (1,x))
          return arr1
      # 方法二 计数排序法
      def relativeSortArray2(self,arr1: List[int], arr2: List[int]) -> List[int]:
          upper = max(arr1)
          frequency = [0] * (upper + 1)
          for x in arr1:
              frequency[x] += 1
          
          ans = list()
          for x in arr2:
              ans.extend([x] * frequency[x])
              frequency[x] = 0
          for x in range(upper + 1):
              if frequency[x] > 0:
                  ans.extend([x] * frequency[x])
          return ans
  # 通过sort()参数指定键排序
  arr1,arr2 = [2,3,1,3,2,4,6,7,9,2,20,19,5,1],[2,4,3,6]
  print(Solution().relativeSortArray(arr1,arr2))