编程珠玑十一章课后题答案

1 

通过排序来查找数组的最大值和最小值通常属于过度使用。习题9说明了不使用排序也能够很快的找出中值，但是在某些系统上使用排序更容易一些。排序对于求众数很有效，但是用散列的速度可能更快。求均值的算法的时间通常正比于n，但是如果先进行一轮排序可能有助于提高数值精度。

2

要移除循环外的那个交换操作，把之前的遍历数组改为从右往左遍历。

#include<iostream>
using namespace std;
void quicksort(int a[],int start,int end)
{
	if(start>end)
		return;
	int m=a[start];
	int index=end+1;
	for(int i=end;i>=start;i--)
	{
	if(a[i]>=m)
	{
		int temp=a[i];
		a[i]=a[--index];
		a[index]=temp;
	}
	}
	quicksort(a,start,index-1);
	quicksort(a,index+1,end);
}   
int main()
{
	int a[]={2,5,3,1,7,6,9,8,10};
	int length=sizeof(a)/sizeof(int);
	quicksort(a,0,length-1);
	for(int i=0;i<length;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}

http://blog.csdn.net/wordwarwordwar/article/details/39082313

9

O(n)时间内从数组中找出第K个最小的元素。

#include<iostream>
using namespace std;
bool Invalidinput=false;
int partition(int a[],int start,int end)
{
	int m=a[start];
	int index=end+1;
	for(int i=end;i>=start;i--)
	{
		if(a[i]>=m)
		{
			int temp=a[i];
			a[i]=a[--index];
			a[index]=temp;
		}
	}
	return index;
}

int SelectKmin(int a[],int start,int end,int k)
{
	if(start>end||k-1<start||k-1>end)
	{
		Invalidinput=true;
		return 0;
	}
	int result=partition(a,start,end);
	while(result!=k-1)
	{
		if(result>k-1)
		{
			result=partition(a,start,result-1);
		}
		else
		{
			result=partition(a,result+1,end);

		}
	}
	return result;
}
int main()
{  
	int a[]={2,3,4,1,5,10,9,7,8,6};  
	int length=sizeof(a)/sizeof(int);
	int k=3;
	int index=SelectKmin(a,0,length-1,k);
	if(!Invalidinput)
		cout<<a[index]<<endl;
	return 0;
}