按照减治法的思路，假设n-1个队伍已经排好序，将第n个队伍插入序列的方法是:
扫描n-1序列，若第n个队伍赢过待扫描的队伍，则插入到这个队伍之前，否则，扫描下一个，直到第n个队伍赢过的队伍为止，插入该队伍之前，没有找到，则插入到n-1队伍最后。
这个问题的算法可以从任意1个队伍开始，直到全部队伍完成插入，由于最坏情况下，一个队伍需要扫描当前已排序的每个队伍，也就是所需要扫描1＋2+3+...+n-1次，总的比较次数就是O(n2)。
按照减治法的思路，假设n-1个队伍已经排好序，将第n个队伍插入序列的方法是:
扫描n-1序列，若第n个队伍赢过待扫描的队伍，则插入到这个队伍之前，否则，扫描下一个，直到第n个队伍赢过的队伍为止，插入该队伍之前，没有找到，则插入到n-1队伍最后。
这个问题的算法可以从任意1个队伍开始，直到全部队伍完成插入，由于最坏情况下，一个队伍需要扫描当前已排序的每个队伍，也就是所需要扫描1＋2+3+...+n-1次，总的比较次数就是O(n2)。
名师互学网 版权所有 (c)2021-2022 ICP备案号：晋ICP备2021003244-6号
