元素比较次数与元素初始排列无关是哪种排列法
1个回答
展开全部
冒泡排序:最好情况需比较n-1次,最坏情况需比较n(n-1)/2;
选择排序:最好情况需比较n(n-1)/2,最坏情况需比较n(n-1)/2;
对分排序:最好情况需比较n/2logn,最坏情况需比较近似nlogn;
根据算法本身,通过计算迭代次数,或建立递推方程求解。
归并排序的比较次数介于(nlogn)/2和(nlogn)-n+1。
如果以大O表示法的话,O((nlogn)/2)=O((nlogn)-n+1)=O(nlogn)。因此,正如chiconysun所说,最好和最坏相差接近2倍,但是最好、最坏和平均的时间复杂度都是O(nlogn) 。
扩展资料:
选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换。
参考资料来源:百度百科-选择排序法
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询