Sorting in Linear Time

算法导论

We also note that
the comparisons ai aj , ai  aj , ai > aj , and ai < aj are all equivalent in that they yield identical information about the relative order of ai and aj . We therefore
assume that all comparisons have the form ai aj .

8.1

任何的比较排序，最坏的结果都会是$n lg n$

解释一下，n!是所有可能的排序的数目，排列组合得来，比如三个数一共有多少种组合方法。。。
$2^h$就是叶子数，每多一层就*2

8.1-1

What is the smallest possible depth of a leaf in a decision tree for a comparison
sort?
n最少要比较n次（在排好的情况下）

8.1-2

Obtain asymptotically tight bounds on lg.nŠ/ without using Stirling’s approximation.
Instead, evaluate the summation Pn
kD1 lg k using techniques from Section
A.2.
???

8.1-3

Show that there is no comparison sort whose running time is linear for at least half
of the nŠ inputs of length n. What about a fraction of 1=n of the inputs of length n?
What about a fraction 1=2n?
额，题目都看不懂

8.1-4

Suppose that you are given a sequence of n elements to sort. The input sequence
consists of n=k subsequences, each containing k elements. The elements in a given
subsequence are all smaller than the elements in the succeeding subsequence and
larger than the elements in the preceding subsequence. Thus, all that is needed to
sort the whole sequence of length n is to sort the k elements in each of the n=k
subsequences. Show an .n lg k/ lower bound on the number of comparisons
needed to solve this variant of the sorting problem. (Hint: It is not rigorous to
simply combine the lower bounds for the individual subsequences.)
不是简单组合
不可以$n/k\ k\ lgk=nlgk$?

8.2 Counting(计数) sort

Counting sort assumes that each of the n input elements is an integer in the range
0 to k, for some integer k. When k= O(n), the sort runs in $\theta (n)$ time.

void COUNTING-SORT(int A[],int l1,int B[],int l2,int k){//假设这个k代表A中最大的数
    k++;//加上0
    int *C=(int*)malloc(sizeof(int)*(k));//
    for(int i=0;i<k;i++){
        C[i]=0;
    }
    for(int j=0;j<l1;j++){
        C[A[j]]=C[A[j]]+1;
    }
    for(int i=1;i<k;i++){
        C[i]=C[i]+C[i-1];
    }
    for(j=l1;j>0;j--){
        B[C[A[j]]]=A[j];
        C[A[j]]=C[A[j]]-1;
    }
}

时间复杂度是$\theta (n)$
分析过程略
特点是：numbers with the same
value appear in the output array in the same order as they do in the input array.
十分稳定

8.2-1

Using Figure 8.2 as a model, illustrate the operation of COUNTING-SORT on the
array A D h6; 0; 2; 0; 1; 3; 4; 6; 1; 3; 2i.
见代码

8.2-2

Prove that COUNTING-SORT is stable.
不管顺序是怎么样时间都不会变，相同元素的位置关系也不会变

8.2-3

Suppose that we were to rewrite the for loop header in line 10 of the COUNTINGSORT
as
10 for j D 1 to A:length
Show that the algorithm still works properly. Is the modified algorithm stable?
相同元素的位置相反，因为C数组里面是-1，除非从某个数开始加。。。（不是从0）

8.2-4

Describe an algorithm that, given n integers in the range 0 to k, preprocesses its
input and then answers any query about how many of the n integers fall into a
range Œa : : b in O.1/ time. Your algorithm should use ‚.n C k/ preprocessing
time.
看起来把上面的算法改一改就可以了。。。只要把C数组（没有累加之前的，初始的）在这个区间的元素加起来

8.3基数排序

从最低位开始排序到最高位，Lemma8.4没看懂

8.3-1

Using Figure 8.3 as a model, illustrate the operation of RADIX-SORT on the following
list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB,
BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.
。。。

8.3-2

Which of the following sorting algorithms are stable: insertion sort, merge sort,
heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm
stable. How much additional time and space does your scheme entail?

8.3-3

Use induction to prove that radix sort works. Where does your proof need the
assumption that the intermediate sort is stable?

8.3-4

Show how to sort n integers in the range 0 to n3  1 in O.n/ time.

8.3-5 ?

In the first card-sorting algorithm in this section, exactly how many sorting passes
are needed to sort d-digit decimal numbers in the worst case? How many piles of
cards would an operator need to keep track of in the worst case?

8.4 Bucket sort

大约如此