解答算法导论问题8-2

来源：百度知道 编辑：UC知道 时间：2024/05/31 22:28:11
Problems 8-2: Sorting in place in linear time :
Suppose that we have an array of n data records to sort and that the key of each record has the value 0 or 1. An algorithm for sorting such a set of records might possess some subset of the following three desirable characteristics:
1. The algorithm runs in O(n) time.
2. The algorithm is stable.
3. The algorithm sorts in place, using no more than a constant amount of storage space in addition to the original array.
a. Give an algorithm that satisfies criteria 1 and 2 above.
b. Give an algorithm that satisfies criteria 1 and 3 above.
c. Give an algorithm that satisfies criteria 2 and 3 above.
d. Can any of your sorting algorithms from parts (a)-(c) be used to sort n records with b bit keys using radix sort in O(bn) time? Explain how or why not.
Suppose that the n records have keys in the range from 1 to k. Show how to modify counting sort so that the records can be sorted in place in O(n + k) ti

a.Counting sort
b.Similiar to parition procedure, traverse and swap 1,0
c.Quicksort
d.Use a or b, each time the sorting method uses O(n), there is b-bit, so the total time is O(bn)
e.Not stable
int[] c = new int[k + 1];
int i = 0;
for (; i < c.length; ++i) {
c[i] = 0;
}
for (i = 0; i < a.length; ++i) {
++c[a[i]];
}
for (i = 1; i < c.length; ++i) {
c[i] += c[i - 1];
}
for (i = k; i >= 1; --i) {
a[c[i] - 1] = i;
--c[i];
}