入排序 折半插0(n2) 0(n2) 0(1) 稳定 入排序 二路插0(n2) 稳定 入排序 表插入0(n2) 0(n2) 0(1) 稳定 排序 起泡排0(n2) 0(n2) 0(1) 稳定 序 直接选0(n2) 0(n2) 0(1) 不稳 2,2’,1 择排序 定 希尔排0(n23) 0(1) 不稳|3,2,2,1(d=2,d=1) 序 定 快速排0( nlog2n) 0(logn)不稳 2,2’,1 序 定 堆排序0( nlog2n)0( nlog2n) 0(1) 不稳|2,1,1’(极大堆) 定 2-路归0( nlog2n)0( logan) 稳定 并排序 基数排 0(rd)稳定 (d*(rd+n 3.这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前 后发生了变化,而题中叙述和排序中稳定性的定义无关,所以此说法不对。对4,3,2,1 起泡排序就可否定本题结论 4.可以做到。取a与b进行比较,c与d进行比较。设a>b,cd(a<b和c<d情况类似),此 时需2次比较,取b和d比较,若b>d,则有序a>b)d;若b<d时则有序c>d>b,此时已进 行了3次比较。再把另外两个元素按折半插入排序方法,插入到上述某个序列中共需4次比 较,从而共需7次比较。 5.本题答案之一请参见第9章的“四、应用题”第70题,这里用分治法求解再给出另一参 考答案 对于两个数x和y,经一次比较可得到最大值和最小值:对于三个数x,y,z,最多经3 次比较可得最大值和最小值;对于n(n>3)个数,将分成长为n-2和2的前后两部分A和B, 分别找出最大者和最小者:MaxA、Min、Mxs、Min,最后Max=Max,Max}和Min={Min,Min}。 对A使用同样的方法求出最大值和最小值,直到元素个数不超过3。设C(n)是所需的最多 比较次数,根据上述原则,当n>3时有如下关系式 n=3 C(n)=C(n-2)+3n>3 通过逐步递推,可以得到:C(n)「3n/2}2。显然,当n>=3时,2n-3>3n/2-2。事实上, 「3n/22是解决这一问题的比较次数的下限 6.假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个,则描述n个 记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子,则说明尚有两种状态没 有分辨出来。我们知道,若二叉树高度是h,则叶子结点个数最多为2;反之,若有u个入排序 折半插 入排序 O（n 2） O（n 2） O（1） 稳定 二路插 入排序 O（n 2） O（n 2） O（n） 稳定 表插入 排序 O（n 2） O（n 2） O（1） 稳定 起泡排 序 O（n 2） O（n 2） O（1） 稳定 直接选 择排序 O（n 2） O（n 2） O（1） 不稳 定 2,2’,1 希尔排 序 O（n 1.3） O（n 1.3） O（1） 不稳 定 3,2,2’,1(d=2,d=1) 快速排 序 O（nlog2n） O（n 2） O（log2n） 不稳 定 2,2’,1 堆排序 O（nlog2n） O（nlog2n） O（1） 不稳 定 2,1,1’(极大堆) 2-路归 并排序 O（nlog2n） O（nlog2n） O（n） 稳定 基数排 序 O ( d*(rd+n) ) O ( d*(rd+n) ) O (rd ) 稳定 3. 这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、 后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对 4，3，2，1 起泡排序就可否定本题结论。 4. 可以做到。取 a 与 b 进行比较，c 与 d 进行比较。设 a>b,c>d(a<b 和 c<d 情况类似)，此 时需 2 次比较，取 b 和 d 比较，若 b>d，则有序 a>b>d；若 b<d 时则有序 c>d>b，此时已进 行了 3 次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需 4 次比 较，从而共需 7 次比较。 5. 本题答案之一请参见第 9 章的“四、应用题”第 70 题，这里用分治法求解再给出另一参 考答案。 对于两个数 x 和 y，经一次比较可得到最大值和最小值；对于三个数 x,y,z，最多经 3 次比较可得最大值和最小值；对于 n(n>3)个数，将分成长为 n-2 和 2 的前后两部分 A 和 B， 分别找出最大者和最小者：MaxA、MinA、MaxB、MinB，最后 Max={MaxA,MaxB}和 Min={MinA,MinB}。 对 A 使用同样的方法求出最大值和最小值，直到元素个数不超过 3。设 C(n)是所需的最多 比较次数，根据上述原则，当 n>3 时有如下关系式： C(n)=      − +  = = ( 2) 3 3 3 3 1 2 C n n n n 通过逐步递推，可以得到：C(n)=3n/2-2。显然，当 n>=3 时，2n-3>3n/2-2。事实上， 3n/2-2 是解决这一问题的比较次数的下限。 6. 假定待排序的记录有 n 个。由于含 n 个记录的序列可能出现的状态有 n!个，则描述 n 个 记录排序过程的判定树必须有 n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没 有分辨出来。我们知道，若二叉树高度是 h，则叶子结点个数最多为 2 h-1；反之，若有 u 个