作业帮 > 数学 > 作业

希尔排序法增量的选取有一句这样说,除1外,无其它公约数,

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/09/01 18:31:34
希尔排序法增量的选取有一句这样说,除1外,无其它公约数,
因为希尔排序要分组,如果增量序列之间的最大公约数大于1,则可能会造成前面一趟(或者某趟)分在同一组已经比较过的关键字,在本趟继续分在同一组,此时这些关键字相互的再次比较纯粹是浪费并无意义,只能增加算法的时间
因此当增量间的最大公约数为1(通称互质)时,就能尽可能地打乱原有的序列,让尽可能多的从未比较过的关键字进行比较