如何不使用sort对大文件按行长度排序并优化性能？

你的代码核心问题是时间复杂度过高：每次遍历找最长元素是O(n)，循环n次加上每次list.remove()的O(n)操作，总复杂度为O(n²)，处理超大文件时必然慢到无法接受。必须重构代码，改用优先队列（Priority Queue）实现O(n log n)的时间复杂度，才能把运行时间压到3秒以内。

优化思路 #

1. 用优先队列替代线性查找：Python的queue.PriorityQueue（或更高效的heapq模块）可在O(log n)时间内获取优先级最高的元素，整体排序复杂度降为O(n log n)。
2. 逐行读取文件：避免一次性把超大文件加载到内存，减少内存占用同时提升读取效率。
3. 小顶堆转大顶堆逻辑：Python优先队列默认是小顶堆，存储(-字符串长度, 字符串)，最小的负长度对应最长的字符串，弹出时就能按从长到短的顺序获取元素。

优化后的代码 #

方案1：使用queue.PriorityQueue（符合作业要求的接口） #

from queue import PriorityQueue

def sort_lines_by_length(originalFile, destinationFile):
    pq = PriorityQueue()
    
    # 逐行读取文件，加入优先队列
    with open(originalFile, 'r') as ogfile:
        for line in ogfile:
            line_stripped = line.rstrip('\n')
            pq.put((-len(line_stripped), line_stripped))
    
    # 从优先队列取出元素，写入目标文件
    with open(destinationFile, 'w') as destfile:
        while not pq.empty():
            _, longest_line = pq.get()
            destfile.write(longest_line + '\n')

方案2：使用heapq（更高效的优先队列实现） #

如果作业允许用heapq（Python底层的优先队列实现），速度会比PriorityQueue更快（后者是线程安全的，有额外锁开销）：

import heapq

def sort_lines_by_length(originalFile, destinationFile):
    heap = []
    
    with open(originalFile, 'r') as ogfile:
        for line in ogfile:
            line_stripped = line.rstrip('\n')
            heapq.heappush(heap, (-len(line_stripped), line_stripped))
    
    with open(destinationFile, 'w') as destfile:
        while heap:
            _, longest_line = heapq.heappop(heap)
            destfile.write(longest_line + '\n')

额外优化点 #

• 避免全量加载文件：原代码courses.split('\n')会把整个文件读入内存再分割，逐行读取更适合超大文件场景。
• 用with管理文件资源：自动关闭文件，避免资源泄漏，代码更简洁。
• 兼容空行处理：原文件中的空行（长度为0）会自动排在结果末尾，无需额外处理。

内容的提问来源于stack exchange，提问作者Pretzel913