华为OD机试真题：按身高和体重排队问题深度解析

华为OD机试真题：按身高和体重排队问题深度解析

问题概述

“按身高和体重排队”问题通常会给定一组学生的身高和体重数据，要求按照身高由低到高、身高相同则按体重由轻到重的顺序进行排序，并输出排序后的学生编号。这是一种常见的排序问题，考察了应试者对排序算法的理解和应用能力。

问题分析与解法

1. 问题建模

• 数据结构: 可以用一个结构体或类来表示每个学生，包含身高、体重和编号等信息。
• 排序规则: 首先按照身高升序排序，对于身高相同的学生，再按照体重升序排序。如果身高和体重都相同，则保持原来的编号顺序。

2. 算法选择

• 自定义排序函数: 可以自定义一个比较函数，按照身高和体重两个条件进行比较。
• 快速排序、归并排序等: 这些经典排序算法都可以用来解决这个问题，但需要在比较函数中加入身高和体重的比较逻辑。
• 优先队列（堆）： 可以将学生信息按照身高和体重构建一个最小堆，然后依次取出堆顶元素。

3. 算法实现

class Student:
    def __init__(self, height, weight, id):
        self.height = height
        self.weight = weight
        self.id = id

def compare(a, b):
    if a.height != b.height:
        return a.height - b.height
    else:
        return a.weight - b.weight

# 使用Python内置的sorted函数
students.sort(key=lambda x: (x.height, x.weight))

# 或者使用自定义的排序函数
students.sort(key=functools.cmp_to_key(compare))

应用场景

• 学生成绩排名: 按照多个指标（如语文成绩、数学成绩）对学生进行综合排名。
• 商品排序: 根据价格、销量等多个维度对商品进行排序。
• 数据分析: 对多维数据进行排序和分组。

扩展与优化

• 稳定性: 对于身高和体重都相同的学生，保持原来的编号顺序，保证排序的稳定性。
• 效率: 对于大规模数据，可以考虑使用更快的排序算法，如快速排序、归并排序。
• 复杂排序规则: 可以根据实际需求，加入更多的排序条件。

华为OD机试备考建议

• 理解排序算法: 掌握快速排序、归并排序、堆排序等经典排序算法的原理和实现。
• 熟悉自定义排序函数: 了解如何使用自定义排序函数来实现复杂的排序规则。
• 注意细节: 在实现排序算法时，注意边界条件和特殊情况的处理。
• 多练习: 多做排序相关的题目，提高代码实现能力。

总结

“按身高和体重排队”问题考察了应试者对排序算法的理解和应用能力。通过对这个问题的深入理解，可以帮助我们更好地掌握排序算法的原理和实现，并在实际开发中应用。