12-5.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"
typedef int DataType;
void Swap(DataType *a,DataType *b)
{
	DataType *t=a;
	*a=*b;
	*b=*t;
}
DataType FSelect(DataType a[], int n, int k)
{// 返回a [0: n-1]中第k小的元素
	//假定a[n] 是一个伪最大元素
	if (k<1||k>n)
	{
		printf("超出边界");
		exit(1);
	}
	return select(a,0,n-1,k);
}
DataType select(DataType a[], int l, int r, int k)
{// 在a [ l : r ]中选择第k小的元素
	int i,j;
	DataType pivot;
	if (l >= r) return a[l];
		i = l, // 从左至右的游标
	j=r+1; // 从右到左的游标
	pivot = a[l];
	// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换
	while(1) {
		do{// 在左侧寻找>= pivot 的元素
			i = i + 1;
		} while(a[i]<pivot);
		do {// 在右侧寻找<= pivot 的元素
			j = j - 1;
		} while (a[j] > pivot);
		if (i >= j) 
			break; // 未发现交换对象
		Swap(&a[i],&a[j]);
	}
	if (j - l + 1 == k) 
		return pivot;
	// 设置p i v o t
	a[l] = a[j];
	a[j] = pivot;
	// 对一个段进行递归调用
	if (j - l + 1 < k)
		return select(a, j+1, r, k-j+l-1);
	else 
		return select(a, l, j-1, k);
}
void main()
{
	DataType a[10];
	//初始化a[10];
	DataType sel=FSelect(a,10,7);
}