1. 哈希排序：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

    2. 桶排序：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]))

3. 快速排序：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]])

4. 插入排序：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

5. 冒泡排序：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

6. 堆排序：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)

    7. 两个数组相对排序

    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))
Copyright © 2021 zbmain.  all right reserved，powered by Gitbook本页修订时间： 2021-04-10

results matching ""

    No results matching ""