希尔排序效率的真实性拟合尝试——Sedgewick增量序列(1982)

摘要

为了对复杂性未知的希尔排序算法进行合理、可信的数值估计，提出拟合不变性结合拟合准确性和显著性的拟合思想和方法，并对采用Sedgewick增量序列4倡22i＋3倡2i＋1的希尔排序算法的平均比较次数进行了数值估计，从cnαlnβ（ n）形式开始，在规模为104～108的测试数据的不同区段分别拟合，根据拟合参数的变动特点，进行合理推断并再次拟合及验证，从而逐步分离和确定出α＝1， c＝1，β＝1．41，最终获得了对各区段拟合几乎不变的结果nln1．41（ n）．拟合方法本身的正确性用已知结果的排序数据进行了验证．