Sorting without Comparison

总结一下非比较排序。

1.      Counting sort

当key值集中在区间[a,b]，且(b-a)/n比值不大时，Counting sort将获得O(n)的时间性能。或者，key值经过某种hash转换，密集分布在[a,b)间时，Counting sort是最佳选择。缺点是非in sort，即需要非常量的额外空间。

void counting_sort( int* A,int size,int a, int b )

{

 int *C = new int[b-a];

 int *B = new int[size];

 for( int *iter = A; iter<A+size; ++iter )  // n

    ++C[*iter];    // C[i]表示a+i值的个数；

 for( int *iter = C+1; iter<C+b-a; ++ iter ) // b-a = k

    *iter+=*(iter-1); // C[i]现在表示小于等于a+i的值的个数

 for( int *iter = A+size-1; iter>=A; --iter )// n

     {

B[C[*iter]] = *iter; // B是排好序的

C[*iter]--; //处理key值重合

 for( int i = 0; i<size; ++i ) //T(n) = O( k+2n ) = O(n)

     A[i]=B[i];

 delete []C,delete []B;

 return;

}

2.      radix_sort

复杂度为O(d(n+k)),其中d为位数，k为每位的基数(即选择数)。

当d是小而k是O(n)级别时，复杂度较小。

 

radix_sort的变种，是对于n个b位二进制数的排序。将b位按每r位一组看成是一个数，则b位分成b/r位，每位有2^r个选择。用radix_sort的复杂度变为：O(b/r(n+2^r).

当b<lgn时，即n个数字中有不少重复时，选r=b,radix_sort将获得O(n)的性能。

当b>=lgn地，选r=lgn最优,将获得bn/lgn的性能，优于比较法的nlgn最优法。由此也可看出，当b较大时，即n个数字较稀时，不适合用radix_sort.

另外，radix_sort不是in_sort,在空间要求严格时，将很郁闷。

Master Theorem: Master Theorem是征对递推式推出算法时间复杂度的有力工具，归纳如下：

若时间复杂度满足递归式：  T(n) = aT(n/b) + f(n)

1)若 n^(logba) > f(n), 则T(n) = n^(logba)

2)若 n^(logba) < f(n), 则T(n) = f(n)

3)若 n^(logba) = f(n), 则T(n) = n^(logba)*lgn

n^(logba)表示n的logba次方,logba = lga/lgb 

需要注意的是，上述的>,<,=,指的是指数级的大小，而非常数级或对数级的差别。

(n)给2个小球，一个100层的楼，要求用最少的掉落次数确定出球能够掉落而不摔坏的楼层数（在测试过程中，两个球都可以被摔坏）。在最坏的情况下，需要试验多少次？(每一次球出手算试验一次)

 

1.此问题有最优子解结构

记 T(n)为n层上最少的实验次数 使得一定可以判断出损坏的楼层。

若第一次在第1层试，碎，不用再试；不碎，则还有两个球，要测n-1层。worst=max(1,T(n-1)+1);

若第一次在第2层试，若碎，则另一球需要放到第一层试;若不碎，则余两球，要测从第三层到第n层共n-2层worst = max( 2,T(n-2)+1 );

若第一次在第a层试，则worst = max( a, 1+T(n-a) );

显然，要T(n)最优，T(n-a)需要最优。

2.此问题从最优子解中做，选择

T(n) = min( max(a,1+T(n-a) )(0<a<n)

 

故此问题是典型的dynamic programming.

T(0) = 0;
T(1) = 1;

T(n) = min( max(a,1+T(n-a) )(0<a<n)

由计算机得, T(0)...T(100)为:

0       1       2       2       3       3       3       4       4       4
4       5       5       5       5       5       6       6       6       6
6       6       7       7       7       7       7       7       7       8
8       8       8       8       8       8       8       9       9       9
9       9       9       9       9       9       10      10      10      10
10      10      10      10      10      10      11      11      11      11
11      11      11      11      11      11      11      12      12      12
12      12      12      12      12      12      12      12      12      13
13      13      13      13      13      13      13      13      13      13
13      13      14      14      14      14      14      14      14      14
14