首页 > 试题广场 >

假设待排序序列的初始排序是正序的,则直接插入排序、直接选择和

[问答题]
假设待排序序列的初始排序是正序的,则直接插入排序、直接选择和冒泡排序那一个更好?反序呢?为什么?

正序:直接插入排序和冒泡排序更好。这种情况下每个元素只需比较一次,即时间复杂度为O(n),而直接选择排序的时间复杂度与初态无关,始终为O(n^2). 逆序:直接选择排序更好。此时三种算法的比较次数均为O(n^2),但是直接插入排序和冒泡排序元素的移动次数为O(n^2),而直接选择排序的移动次数为O(n).
发表于 2022-11-29 19:27:23 回复(0)