＞第 11 章 排序与查找＞线性查找＞习题

习题中的第三题找第K小的算法还是nlng的复杂度啊，partition的复杂度是n没错，后面的递归调用跟前面的快排比起来，无非是两个递归分支变成一个递归分支了，复杂度还是一样的啊。。真奇怪
然后我查看了MIT的课程，它用的是随机划分，伪代码是
Randomized-Partition(A, p, q)
  swap(A[p], A[rand(p,q)]) // the only thing changed in the original Partition subroutine!
  x = A[p]
  i = p
  for j = p+1 to q
    if A[j] <= x
      i = i+1
      swap(A[i], A[j])
  swap(A[p], A[i])
  return i


Randomized-Select(A, p, q, k) // finds k-th smallest element in array A[p..q]
  if p == q
    return A[p]
  r = Randomized-Partition(A, p, q)
  n = r - p + 1
  if k == n
    return A[r]
  if k < n
    return Randomized-Select(A, p, r-q, k)
  else
    return Randomized-Select(A, r+1, q, k-n)

两个分支变成一个分支了，时间复杂度还是一样的？那是你想当然的。你再仔细想想能一样吗。另外，算法导论上应该有这个时间复杂度的分析。本书是一本基础书，不能在这方面深入展开了。

确实，在第几次循环return是不确定的，因此乘上概率，这样粗略能降一次。树的最大深度是Θ(n),单支，算法果然要慢慢想，哎。

你可以这样想（假设每次找到的pivot都刚好是中点）：
找第k小的算法，每次丢掉一半，第一层处理n个，第二层处理n/2个，第三层处理n/4个……一共处理n+n/2+n/4+...=2n个，所以是Θ(n)
快速排序，第一层处理n个，第二层分两组，每组处理n/2个，加起来还是n个，同理，第三层也是n个，每层都处理n个，一共处理lgn层，所以是Θ(nlgn)

第三题：

#include <stdio.h>
#define N 7
int a[N] = {3, 9, 5, -4, 4, 3, 2};
void exchange(int i, int j){
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

int order_statistic(int start, int end, int k){
	int select = a[end-1];
	int i = start;
	int j = end - 2;
	while (i <= j) {
		while (a[i] < select) i++;
		while (a[j] >= select) j--;
		if (i < j) {
			exchange(i, j);
		} else {
			break;
		}
		i++;
		j--;
	}
	exchange(i, end-1);
	if (k == i) {
		return a[k];
	} else if (k > i) {
		return order_statistic(i+1, end, k);
	} else {
		return order_statistic(start, i, k);
	}
}

	
int main(void){
	int k; 
	scanf("%d", &k);
	int i;
	for (i = 0; i < N; i++) printf("%d ", a[i]);
	printf("\n");
	printf("you find %d of array\n", k);
	printf("the answer is: %d\n", order_statistic(0, N, k));
}

如果您有建设性意见，哪怕只是纠正一个错别字，也请不吝赐教，您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见！