chap8 线性时间排序

决策树模型 计数排序 基数排序 桶排序 算法导论

内容

比较排序的下界

1. 在排序的最终结果中，各元素的次序依赖于他们之间的比较
2. 最坏情况下，任何比较排序都要经过$\Omega(n\lg n)$次比较
3. 比较排序可以抽象成一棵决策树，排序算法的执行对应于一条从树的根结点到叶结点的路径，因此比较操作次数的下线就是树的深度
4. 由于归并排序和堆排序在最坏情况的上界是$\Omega(n\lg n)$，因而是渐进最优的，热河一直的比较排序最多就是在常数因子上优于它们

计数排序

1. 计数排序：假设n个输入元素中的每一个都是位于$[0,k]$内的一个整数，当$k=O(n)$时，排序的运行时间是$\Theta(n)$
2. 基本思路，对于每一个输入元素x，统计不大于x元素的个数，这样就可以确定需要将x放置的位置
3. 伪代码，输入数组A，返回排好序的数组B

Counting-Sort(A,B,k)——$\Theta(n+k)$

let C[0...k] be a new array with each element equal to 0
for j = 1 to A.length
    C[A[j]] = C[A[j]] + 1 #让C[i]表示A中值等于i的元素的个数
for i = 1 to k
    C[i] = C[i] + C[i-1] # 让C[i]表示A中值不大于i的元素的个数
for j = A.length to 1 # 反序以保持稳定性
    B[C[A[j]]] = A[j]
    C[A[j]] = C[A[j]] - 1

基数排序

1. 基数排序：假设n个输入元素中的每一个都是位于$[0,k]$内的一个整数，当$k=O(n)$时，排序的运行时间是$\Theta(n)$
2. 基本思路，
3. 伪代码

桶排序

1. 桶排序：假设输入数据服从均匀分布，平均情况下算法的运行时间是$\Theta(n)$（条件可以减弱成所有桶的大小的平方和与总的元素呈线性关系）
2. 基本思路， 可以看成是 6.5-6k路归并的变形，在这里，各个链表之间是相关联的——存在大小关系
3. 伪代码，

Bucket-Sort(A)——$\Theta(n)$

n = A.length
let B[0...n-1] be a new array
for i = 0 to n-1
    make B[i] an empty list
for i = 1 to n
    insert A[i] into list B[nA[i]] #向下取整
for i = 1 to n-1
    sort list with insertion sort
contatenate the lists together in order

习题中的算法

8-2 线性时间原址排序

原址但不稳定
Counting-Sort-inPlace(A,k)

let C[0...k] be a new array with each element equal to 0
for j = 1 to A.length
    C[A[j]] = C[A[j]] + 1 #让C[i]表示A中值等于i的元素的个数
p = 0 # 标记将要改写数据的位置
for i = 0 to k
    for j = 0 to C[i]
        p = p + 1
        A[p] = i

8-3 变成数据项的排序

a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array
is n. Show how to sort the array in $O(n)$ time.

1. counting every number's digits --$O(n)$
2. sort the integers by number of digits by using counting-sort --$O(n)$
3. use radix-sort to sort each group of integers with the same digits

b. You are given an array of strings, where different strings may have different
numbers of characters, but the total number of characters over all the strings
is n. Showhowto sort the strings in $O(n)$ time.
(Note that the desired order here is the standard alphabetical order; for example,
dfuioasdfiousiodf

1. using counting-sort to sort the strings bt first letter--$O(n)$
2. putting the strings with the same first letter into one group and remove the first letter
3. using counting-sort to sort each group on the way of 1 and reapeat until each group has only one string

8-4 水壶问题

1. 题目描述：本质上就是将包含n个数的集合，随机打乱顺序变成两个数组，这两个数组所含的元素都是相同的，但是顺序不同。题目要做的就是，选定一个数组，将另一个数组中元素的位置调整至与该数组相同
2. 思路1，随机选取red中的某个数r，利用人将blue分成三部分，大于r的b+，小于r的b-，以及等于r的b；再反过来利用b对red进行同样操作，对b+,r+和b-,r-递归调用即可

Match-Jugs(R,B)

if |R| = 0
    error "empty"
else if |R| = 1
    let R = {r}, B = {b}
    output (r,b)
    return
else
    r = random(R)
    B+,B-,b
    R+,R-,r
    output (r,b)
    Match-Jugs(R+,B+)
    Match-Jugs(R-,B-)

思路2：
用数组，加上快排的思想。具体做法就是，同时对两个数组进行partition，两者是用的主元相同；同时还需要再partition过程中增加根据主元的值寻找主元在数组中的位置这一操作，为此额外操作付出的时间代价为$\Theta(n\lg n)$，
值得注意的是，这里很容易出错的地方在于，快速排序中的partition，在确定主元后，应立即将主元换到数组的尾端，否则就会出错，因而在这里需要加上在数组中找值的位置这一额外操作

8-5 平均排序

思路
1. 将n个数分成k个子数组，对每个子数组进行排序——$kO(n/k\lg n/k)=O(n\lg n/k)$
2. 对每个子数组，如$S_{i}$，将$S_{i}[j]$插入到$A[i+j*k-k]$的位置

8-7 0-1排序引理和列排序

代码实现

java