计算机二级中的排序方法的比较次数是怎么回事?

发布网友发布时间：2022-04-29 23:28

共1个回答

热心网友时间：2022-06-25 21:58

首先前面的那个是O而不是0，相信你应该了解时间复杂度的表示方法吧，前面就有一个O，我认为此处也应该是和那个一样的含义，即取n的最大次方！下面我们看看堆排序的定义：
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤[n/2] )

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。
看完之后相信你自己就可以解答自己的疑问了！朋友祝你成功！

参考资料：http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.2.1.htm