【16】数据结构之基于树的排序算法篇章

选择排序

• 基本思想：从待排序的序列中选出最大值或最小值，交换该元素与待排序序列的头部元素，对剩下的元素重复操作，直到完成所有元素排序.

简单选择排序

• 第i次排序通过n-i次关键字的比较，从n-i+1个元素中选出关键字最小的元素，并和第i个元素交换.共需进行i-1次比较，直到所有元素排序完成为止.
• 示意图
  
• 代码实现与调试

# 树的排序--简单选择排序
class SelectSort(object):def __init__(self, items):# 待排序的序列self.items = itemsdef selectSort(self):"""简单选择排序:return:"""# 共n轮排序for i in range(len(self.items)):# 待交换的元素index = i# 在未排序的序列中选取最小的元素for j in range(i+1, len(self.items)):if self.items[j] < self.items[index]:index = j# 最小的元素不是带交换的元素，则两者交换if index != i:self.items[i],self.items[index] = self.items[index],self.items[i]if __name__ == "__main__":arr = [84, 62, 35, 77, 55, 14, 35, 98]select = SelectSort(arr)select.selectSort()print(arr)

树形选择排序

• 树形选择排序也称锦标赛排序.
• 首先所有参加比赛的选手两两分组，每组产生一个胜利者，然后这些胜利者再两两分组进行比赛，每组产生一个胜利者，之后重复执行，直到最后只有一个胜利者为止.
• 示意图
  
• 代码实现与调试

class TournamentSort:def __init__(self, arr):self.original = arr.copy()self.n = len(arr)# 初始化所有属性，确保空数组时属性存在self.leaf_size = 0self.tree_size = 0self.tree = []if self.n == 0:return  # 空数组直接返回# 计算扩展到下一个2的幂次方的叶子数量self.leaf_size = 1 << (self.n - 1).bit_length()self.tree_size = 2 * self.leaf_size - 1# 初始化树结构并用inf填充空位self.tree = [float('inf')] * self.tree_size# 将原始数据填充到叶子节点self.tree[-self.leaf_size: -self.leaf_size + self.n] = self.original# 构建初始锦标赛树（自底向上）for i in range(self.tree_size - 1, 0, -1):if i % 2 == 1:  # 只处理左子节点，避免重复计算parent = (i - 1) // 2self.tree[parent] = min(self.tree[i], self.tree[i + 1])def get_min(self):"""获取当前最小值并重构树"""if self.n <= 0:return Nonewinner = self.tree[0]# 查找叶子层中的最小值位置idx = self.tree_size // 2  # 叶子层起始索引while idx < self.tree_size:if self.tree[idx] == winner:breakidx += 1# 标记该位置为已选中self.tree[idx] = float('inf')self.n -= 1# 自底向上更新树结构while idx > 0:parent = (idx - 1) // 2sibling = idx + 1 if idx % 2 == 1 else idx - 1self.tree[parent] = min(self.tree[idx], self.tree[sibling])idx = parentreturn winnerdef sort(self):"""执行完整排序过程"""sorted_arr = []while True:val = self.get_min()if val is None:breaksorted_arr.append(val)return sorted_arrdef print_tree(self):"""可视化打印树结构（调试用）"""print("当前锦标赛树结构：")if self.tree_size == 0:print("空树")returnlevel = 0level_size = 1while level_size <= self.tree_size:start = 2 ** level - 1end = start + level_sizeprint(f"Level {level}: {self.tree[start:end]}")level += 1level_size *= 2# ---------------------- 测试用例 ----------------------
if __name__ == "__main__":test_cases = [[3, 1, 4, 1, 5, 9, 2, 6],  # 常规测试[9, 3, 5, 2, 8],  # 奇数元素[5, 3, 8, 6, 2],  # 重复值测试[1],  # 单个元素[]  # 空数组]for i, case in enumerate(test_cases):print(f"\n测试用例 {i + 1}: {case}")ts = TournamentSort(case)ts.print_tree()  # 调试查看初始树结构sorted_result = ts.sort()print(f"排序结果: {sorted_result}")print("验证结果:", "正确" if sorted_result == sorted(case) else "错误")

堆排序

• 对树形选择排序的一种改进

堆的定义Heap

• 堆是二叉树的一种
• 堆是完全二叉树
• 堆中任意结点的值总是不大于或者不小于其双亲结点的值
• 堆分为大根堆和小跟堆

小跟堆

• 如果根结点存在左孩子结点，则根结点的值小于或等于左孩子结点的值
• 如果根结点存在右孩子结点，则根结点的值小于或等于右孩子结点的值
• 根结点的左右子树也是小跟堆
• 小跟堆示意图
  

大根堆

• 如果根结点存在左孩子结点，则根结点的值大于或等于左孩子结点的值
• 如果根结点存在右孩子结点，则根结点的值大于或等于右孩子结点的值
• 根结点的左右子树也是大跟堆
• 大跟堆示意图
  

堆的存储

• 常用顺序结构进行存储.
• 重建堆方法
  • 首先将完全二叉树根结点中的元素移出，
  • 从空结点的左右孩子结点中选出一个关键字较小的元素，上移到空结点中，
  • 当前那个较小关键字较小的子结点相当于空结点，
  • 重复上述移动原则
  • 直到空结点的左右孩子结点的关键字均不小于待调整元素的关键字为止
• 建立初始堆算法思路
  • 一个任意序列可以看成对应的完全二叉树，由于叶子结点可以视为单元素的堆，然后反复利用重建堆方法，自底向上逐层把所有子树调整为堆，直到将整个完全二叉树调整为堆为止

堆的代码设计

class Heap:def __init__(self, items=[]):self.items = items.copy()self.build_min_heap()def build_min_heap(self):"""将列表初始化为小根堆"""length = len(self.items)for i in range(length // 2 - 1, -1, -1):self._sift_down(i, length)def insert(self, key):"""插入新元素并上浮调整"""self.items.append(key)self._sift_up(len(self.items) - 1)def delete(self):"""删除堆顶元素"""if not self.items:raise IndexError("堆为空，无法删除")# 将最后一个元素移到堆顶removed = self.items[0]self.items[0] = self.items[-1]self.items.pop()# 下沉调整if self.items:self._sift_down(0, len(self.items))return removeddef _sift_up(self, index):"""元素上浮操作"""parent = (index - 1) // 2while parent >= 0 and self.items[index] < self.items[parent]:self.items[index], self.items[parent] = self.items[parent], self.items[index]index = parentparent = (index - 1) // 2def _sift_down(self, index, size):"""元素下沉操作"""smallest = indexleft = 2 * index + 1right = 2 * index + 2if left < size and self.items[left] < self.items[smallest]:smallest = leftif right < size and self.items[right] < self.items[smallest]:smallest = rightif smallest != index:self.items[index], self.items[smallest] = self.items[smallest], self.items[index]self._sift_down(smallest, size)def __str__(self):return str(self.items)# ---------------------- 测试用例 ----------------------
if __name__ == "__main__":# 测试初始化与插入删除heap = Heap([10, 25, 15, 40, 25, 20, 30, 50, 55])print("初始堆:", heap)  # 输出： [10, 25, 15, 40, 25, 20, 30, 50, 55]heap.insert(9)print("插入9后:", heap)  # 输出： [9, 25, 10, 40, 55, 15, 30, 50, 25, 20]val = heap.delete()print(f"删除元素 {val} 后:", heap)  # 删除9后：[10, 25, 15, 40, 55, 20, 30, 50, 25]val = heap.delete()print(f"删除元素 {val} 后:", heap)  # 删除10后：[15, 25, 20, 40, 25, 55, 30, 50]# 测试空堆empty_heap = Heap()try:empty_heap.delete()except IndexError as e:print("空堆删除测试:", e)  # 输出：堆为空，无法删除# 测试单元素堆single_heap = Heap([5])single_heap.delete()print("单元素堆删除后:", single_heap)  # 输出：[]

堆排序的代码设计

class HeapSort:def __init__(self, items):self.items = items  # 初始化待排序数组def heapSort(self):"""堆排序主方法"""length = len(self.items)# 1. 构建最大堆（从最后一个非叶子节点开始调整）for i in range(length // 2 - 1, -1, -1):self._adjust_max_heap(self.items, i, length)# 2. 排序阶段（依次将堆顶元素移到末尾）for i in range(length - 1, 0, -1):# 交换堆顶（最大值）与当前末尾元素self.items[0], self.items[i] = self.items[i], self.items[0]# 调整剩余堆结构（堆大小逐渐减小）self._adjust_max_heap(self.items, 0, i)def _adjust_max_heap(self, arr, root, heap_size):"""调整最大堆（递归实现）"""largest = root  # 初始化最大值为根节点left = 2 * root + 1  # 左子节点索引right = 2 * root + 2  # 右子节点索引# 比较左子节点if left < heap_size and arr[left] > arr[largest]:largest = left# 比较右子节点if right < heap_size and arr[right] > arr[largest]:largest = right# 如果最大值位置变化，交换并递归调整子树if largest != root:arr[root], arr[largest] = arr[largest], arr[root]self._adjust_max_heap(arr, largest, heap_size)# ---------------------- 测试用例 ----------------------
if __name__ == "__main__":nums = [40, 55, 73, 12, 98, 27]sorter = HeapSort(nums)sorter.heapSort()print("排序结果:", nums)  # 输出: [12, 27, 40, 55, 73, 98]

排序算法综合比较