Adaptive Sort

释义 Definition

自适应排序：一种会“利用输入数据中已有的部分有序性”的排序思路或算法特性；当数据越接近有序时，通常运行得更快（例如插入排序在近乎有序时效率很高）。在算法语境中也常说某算法是 adaptive（自适应的）。

发音 Pronunciation

/əˈdæptɪv sɔːrt/

例句 Examples

The app uses an adaptive sort to speed up searches when the list is almost ordered.
当列表几乎已经有序时，这个应用使用自适应排序来加快搜索速度。

Unlike a fixed-time method, an adaptive sort can exploit existing runs in the data to reduce comparisons and swaps.
不同于固定表现的方法，自适应排序可以利用数据中已存在的连续有序段（runs），从而减少比较和交换次数。

词源 Etymology

adaptive 来自拉丁语 adaptare（“使适合、调整”），表示“能根据情况调整的”。sort 来自古法语 sortir（与“分类、分配”相关），在英语中发展出“分类/排序”的含义。合起来 adaptive sort 就是“会根据输入特点而调整表现的排序”。

相关词 Related Words

• Adaptive
• Sorting
• Insertion
• Merge
• Quicksort
• Stable
• In-Place
• Comparison
• Run

文献与作品 Literary Works

• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth）——排序理论中常讨论“利用已有有序性”的思想，与自适应排序相关。
• Algorithms（Robert Sedgewick & Kevin Wayne）——在讲解多种排序算法时，常用“对近乎有序数据更快”等角度介绍自适应性。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）——讨论插入排序等在“几乎有序”输入下的良好表现，常被用来说明排序的自适应特征。