面试题：Python排序算法时间复杂度及性能优化

Question

已知有一个包含大量整数的列表，需要对其进行排序。请使用Python实现至少两种不同的排序算法（如冒泡排序、快速排序），分析每种算法的时间复杂度，并讨论在实际应用场景中如何根据数据规模和特点选择合适的排序算法以优化性能。

Answer 1

冒泡排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1] :
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

时间复杂度：平均和最坏情况为 $O(n^2)$，最好情况为 $O(n)$。

快速排序

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

时间复杂度：平均情况为 $O(nlogn)$，最坏情况为 $O(n^2)$。

算法选择建议

• 小规模数据：冒泡排序实现简单，代码量少，可优先选择。但如果对时间复杂度有要求，即使数据规模小，快速排序平均性能更好。
• 大规模数据：快速排序平均性能优秀，通常选择快速排序。但如果数据几乎有序，冒泡排序最好情况的时间复杂度 $O(n)$ 会更具优势。如果数据分布极端，可能会使快速排序达到最坏时间复杂度，此时可以考虑其他稳定排序算法如归并排序等。