很多人初学排序时先接触冒泡排序但你知道Python的list.sort()底层用的是什么吗它是一种名为Timsort的稳定排序算法时间复杂度O(n log n)专门为处理真实大规模数据而设计。Timsort由Tim Peters于2001年为Python创造现已成为Python、Java、Android及GNU Octave的默认排序算法。它结合了插入排序和归并排序核心思想是利用数据中已存在的有序片段——这些片段被称为run。算法流程若数组长度小于64直接使用插入排序因其对小列表效率极高。否则算法先遍历数组找出天然有序的run升序或降序降序则反转并确定合适的minrun范围32~64使run长度尽量接近2的倍数便于后续归并。若run长度不足minrun则从后续取元素补足并对新元素执行插入排序生成长度为minrun的新run。随后将这些run压入栈中通过规则A B C和B CA、B、C为栈顶三个run控制归并时机以实现平衡与效率。飞奔模式Galloping当归并时一个run连续“获胜”Timsort会进入飞奔模式利用二分搜索快速移动整块数据充分利用数据内部结构大幅提升性能。Timsort的最大优势是充分利用真实数据中的有序性同时保持稳定排序。虽然Python内置版本由C实现但其设计思想值得深入理解亲自实现一次会大有收获。使用只需调用list.sort()或sorted(list)。
