学步园

一、排序

    本章以介绍插入排序为伊始，进而介绍了快速排序，以及随机选取划分元素的改进的快速排序，且可根据所要排序元素的多少动态的选择是进行插入排序还是快速排序的算法（在元素较少的排序中，插入排序的运行效果可能更好）。插入排序与快速排序这里就不多介绍了。下面看一个这一章的习题。

    习题第9题中要求编写一个程序，在O(n)时间内从数组x[0...n-1]中找到第k个最小的元素，算法可以对x当中的元素进行排序。此算法赖子C.A.R. Hoare，是对快速排序算法的一种修改：

#include <stdio.h>
#include <stdlib.h>

void swap(int x[],int a, int b)
{
	int temp = x[a];
	x[a] = x[b];
	x[b] = temp;
}

int randint(int l,int u)
{
	return l+rand()%(u-l+1);
}

void select(int x[],int l,int u,int k)
{
	int i,j,temp,t; 
	if (l>=u)
		return;
	swap(x,l,randint(l,u));
	t = x[l];
	i = l;
	j = u+1;
	while (1)
	{
		do 
		{
			i++;
		} while(i<=u && x[i]<t);
		do 
		{
			j--;
		} while(x[j]>t);
		if (i>j)
			break;
		temp = x[i];
		x[i] = x[j];
		x[j] = temp;
	}
	swap(x,l,j);
	if (j<k)
	{
		select(x,j+1,u,k);
	}
	else if (j>k)
	{
		select(x,l,j-1,k);
	}
}

void main()
{
	int x[8] = {1, -2, 3, 10, -4, 7, 2, -5};
	int k;
	printf("输入要找的第k小元素(0<=k<=7):");
	scanf("%d",&k);
	select(x,0, 7, k);
	printf("%d/n", x[k]);
}

    问题扩展：分治法找第k小元素。找到数组第K小元素后，有且只有x[0]至x[k－1]是比x[k]小的。所以同样算法可解决下面问题，复杂度同为O(n)。

    给定一个具有n个元素的整数集，一个整数t以及一个整数k，如何快速确定该整数集是否存在一具有k个元素的子集，其中各元素的总和至多只能为t？

#include <stdio.h>
#define MAXN 8
int x[MAXN] = {1, -2, 3, 10, -4, 7, 2, -5};

void swap(int a, int b)
{
	int ntemp = x[a];
	x[a] = x[b];
	x[b] = ntemp;
}

int MinK(int l, int h, int k)
{
	if (l > h)
		return 0;

	int m = l;
	for (int i=l+1; i<=h; i++)
	{
		if (x[i] < x[m])
			swap(++m, i);
	}
	swap(m, l);

	if (k == m)
		return x[m];
	else if (k < m)
		return MinK(l, m-1, k);
	else
		return MinK(m+1, h, k);
}

int main(int argc, char* argv[])
{
	//第0小元素是最小元素
	int n = MinK(0, MAXN-1, 6); 
	printf("%d/n", n); 
	return 0;
}

    注：另外，要求一个数组的第k小或者第k大的数则可通过建立最大最小堆来实现，时间复杂度为O(nlogk)。