计算机程序设计的艺术(Sorting I)

计算机程序设计的艺术

• • 计数排序
  • • 比较计数
    • 分布计数

插入排序
* 直接插入排序
* 二叉插入排序与二路插入排序
* Shell 排序
* 链表插值排序
* 地址计算排序（也称作计数排序）

计数排序

比较计数

计数排序的核心思路在于统计每个元素之前出现过的元素数量。一种直接的方式是比较相邻元素以确定大小关系，并对较大的元素进行计数值累加。一种函数计算结果将指示原始元素值应当放置的位置。这一方法被称为基于比较的计数值算法，并由E. H. Friend在1956年的《Journal of the Association for Computing Machinery》中首次提出。该算法的时间复杂度范围大致在二次阶内。

    template <std::totally_ordered T, std::size_t N>
    std::array<unsigned int, N> c_count(std::span<T, N> k)
    {
    	std::array<unsigned int, N> count = { 0 };
    
    	// 两两比较大小，较大者计数加一
    	for (int