# 思考题

## 8-1 比较排序的平均情况下界

a)n个不同的元素对应n!个不同的输入，因此只有这n!个输入所对应的叶结点是有概率的，其余概率均为0。\
由于这n!种输入的出现是等概率的，每一种的都是1/n1，因此其对应的叶结点的概率也是1/n!\
b)设T(n)是一个叶子结点n的在决策树T上的深度，RT(n)、LT(n)分别表示n在T的右、左子树上的深度。\
那么T(n)=RT(n)+1或T(n)=LT(n)+1\
因此D(T)=D(RT)+D(LT)+k\
c)后面这几题，以我有限的智商和数学能力理解不了，也看不懂网上的答案，不写了

## 8-2 以线性时间原地转换排序

a)计数排序\
b)快速排序\
c)稳定排序\
d)基数排序要求所使用的排序方法是满足的（条件2），如果要在O(bn)时间内完成，所使用算法的时间应该是O(n)（条件1），所以只有a可以\
e)不稳定

```
COUNTING-SORT(A, k)
 1    for i <- 0 to k
 2        do C[i] <- 0
 3    for j <-1 to length[A]
 4        C[A[j]] <- C[A[j]] + 1
 5    cnt <- 1
 6    for i <- 1 to k
 7        while C[i] > 0
 8            A[cnt] <- i
 9            C[i] <- C[j] - 1
10            cnt <- cnt + 1
```

## 8-3 排序不同长的数据项

a)先用计数排序算法法按数字位数排序O(n)，再用基数排序的方法分别对每个桶中的元素排序O(n)\
b)递归使用计数排序，先依据第一个字母进行排序，首字相同的放在同一组，再对每一组分别使用计数排序的方法比较第二个字母\
见到有人用字典树，也是可以的

## 8-4 水壶

a)最原始的比较方法，所有的红水壶与所有的蓝水壶依次比较\
c)算法类似于快排，由于不是同种颜色的水壶之间比较，所以采用交叉比较\
step1：从红色水壶中随机选择一个\
step2：以红色水壶为主元对蓝色水壶进行划分\
step3：划分的结果是两个数组，并得到与红色水壶相同大小的蓝色水壶\
step4：以这个蓝色水壶为主元，对红色水壶进行划分\
step5：用step1到step4的过程不断迭代

## 8-5 平均排序

见6.5-8堆排序-K路合并\
a)1排序是完全排序\
b)1，3，2，4，5，7，6，8，9，10\
c)分工展开化简即可\
d)\
step1：分别把1, 1+k, 1+2k, 1+3k,……;2, 2+k, 2+2k, 2+3k,……；……当作是单独的集合\
step2：对每个集合进行排序时间为O(nlg(n/k))\
e)\
step1：同d)step1\
step2：用堆排序进行k路合并

## 8-6 合并已排序列表的下界

a)2n个数，随机选n个数，可选的方法有C(2n,n)种\
b)

```
2^h >= C(2n,n)  
=====>   h >= lg((2n)!) - 2lg(n!)
=====>   h >= 2nlg2n - 2nlgn
=====>   h >= 2nlg2
```

只能推到这了，最后怎么算，还希望高手指点\
c)d)看上去很显然的事情，不知道怎么证


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://windmising.gitbook.io/introduction-to-algorithms/introduction-2/thinking.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.