面试题答案
一键面试归并排序
- 分析:
- 优点:归并排序是一种稳定的排序算法,这意味着相同元素的相对顺序在排序前后保持不变,符合题目中按顺序依次比较元素的要求。其时间复杂度为 (O(n \log n)),在大数据量下表现良好。空间复杂度为 (O(n)),因为需要额外的空间来合并子数组。
- 缺点:需要额外的空间来存储临时数组,在空间紧张的情况下可能不太适用。
- 代码实现:
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
快速排序
- 分析:
- 优点:平均情况下,快速排序的时间复杂度为 (O(n \log n)),性能较高。并且不需要额外的大量空间(空间复杂度在平均情况下为 (O(\log n))),原地排序特性使其在空间利用上有优势。
- 缺点:快速排序是不稳定的排序算法,在最坏情况下时间复杂度会退化到 (O(n^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
使用内置排序函数(优化选择)
- 分析:
- 优点:Python的内置
sorted
函数是经过高度优化的,在大多数情况下性能非常好。并且它是稳定的排序,满足题目要求。它使用的是Timsort
算法,结合了归并排序和插入排序的优点,在不同数据分布下都有较好表现。 - 缺点:可能对于一些特定的、对空间和时间复杂度有极端要求的场景,不能进行定制化的极致优化,但在一般情况下已经足够优秀。
- 优点:Python的内置
- 代码实现:
def builtin_sort_nested(lst):
return sorted(lst, key=lambda x: tuple(x))
在实际应用中,如果对空间复杂度要求不高且需要稳定排序,推荐使用内置的 sorted
函数。如果空间紧张且对稳定性要求不高,快速排序在平均情况下能有较好性能,但需要注意最坏情况。而归并排序在需要稳定排序且对空间有一定容忍度时是不错的选择。