MST

星途 面试题库

面试题:Python列表复杂排序场景下的性能深度剖析

在Python中,若要对嵌套列表进行排序,外层列表包含多个内层列表,每个内层列表又有不同数量的元素,现在需要先根据内层列表的第一个元素进行排序,若第一个元素相同则按第二个元素排序,依此类推。在保证正确性的前提下,如何通过不同排序算法(如归并排序、快速排序等)实现并优化排序性能?请详细分析每种算法在该场景下的优劣,并给出代码实现。
19.9万 热度难度
编程语言Python

知识考点

AI 面试

面试题答案

一键面试

归并排序

  1. 分析
    • 优点:归并排序是一种稳定的排序算法,这意味着相同元素的相对顺序在排序前后保持不变,符合题目中按顺序依次比较元素的要求。其时间复杂度为 (O(n \log n)),在大数据量下表现良好。空间复杂度为 (O(n)),因为需要额外的空间来合并子数组。
    • 缺点:需要额外的空间来存储临时数组,在空间紧张的情况下可能不太适用。
  2. 代码实现
def merge_sort_nested(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left_half = merge_sort_nested(lst[:mid])
    right_half = merge_sort_nested(lst[mid:])
    return merge(left_half, right_half)


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        for k in range(min(len(left[i]), len(right[j]))):
            if left[i][k] < right[j][k]:
                result.append(left[i])
                i += 1
                break
            elif left[i][k] > right[j][k]:
                result.append(right[j])
                j += 1
                break
            elif k == min(len(left[i]), len(right[j])) - 1:
                if len(left[i]) < len(right[j]):
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

快速排序

  1. 分析
    • 优点:平均情况下,快速排序的时间复杂度为 (O(n \log n)),性能较高。并且不需要额外的大量空间(空间复杂度在平均情况下为 (O(\log n))),原地排序特性使其在空间利用上有优势。
    • 缺点:快速排序是不稳定的排序算法,在最坏情况下时间复杂度会退化到 (O(n^2)),例如当每次选择的基准元素都是最大或最小元素时。在题目场景下,由于需要稳定排序,这是一个明显的劣势。
  2. 代码实现
def quick_sort_nested(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[len(lst) // 2]
    left = [x for x in lst if compare(x, pivot) < 0]
    middle = [x for x in lst if compare(x, pivot) == 0]
    right = [x for x in lst if compare(x, pivot) > 0]
    return quick_sort_nested(left) + middle + quick_sort_nested(right)


def compare(a, b):
    for i in range(min(len(a), len(b))):
        if a[i] < b[i]:
            return -1
        elif a[i] > b[i]:
            return 1
    if len(a) < len(b):
        return -1
    elif len(a) > len(b):
        return 1
    return 0

使用内置排序函数(优化选择)

  1. 分析
    • 优点:Python的内置 sorted 函数是经过高度优化的,在大多数情况下性能非常好。并且它是稳定的排序,满足题目要求。它使用的是 Timsort 算法,结合了归并排序和插入排序的优点,在不同数据分布下都有较好表现。
    • 缺点:可能对于一些特定的、对空间和时间复杂度有极端要求的场景,不能进行定制化的极致优化,但在一般情况下已经足够优秀。
  2. 代码实现
def builtin_sort_nested(lst):
    return sorted(lst, key=lambda x: tuple(x))

在实际应用中,如果对空间复杂度要求不高且需要稳定排序,推荐使用内置的 sorted 函数。如果空间紧张且对稳定性要求不高,快速排序在平均情况下能有较好性能,但需要注意最坏情况。而归并排序在需要稳定排序且对空间有一定容忍度时是不错的选择。