2.cpp

数据结构中的基本问题

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++
//堆排序法
//作者：陈健
//学号：200153090313
//院系：信息与计算科学
//platform:windows2000pro+Visual c++ 6.0
++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
#include "stdio.h"
#include "string.h"
#define MAX_LENGTH 8

void Swap(int &a,int &b)
{
	int temp = a;
	a = b;
	b = temp;
	
}

int select(int a[], int l, int r, int k)
{
	if (l >= r) 
	{
		return a[l];
	}
	int i = l;// 从左至右的游标
	int	j = r + 1; // 从右到左的游标
	int pivot = a[l];
	
	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;
		
	}
	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()
{
	int array[MAX_LENGTH],k;

	printf("please enter munbers(less than %d):\n",MAX_LENGTH);
	for(int i=0;i<MAX_LENGTH;i++)
	{
		scanf("%d",&array[i]);
	}
	printf("please enter the n smallest vaule:\n");
	scanf("%d",&k);

	select(array,0,MAX_LENGTH-1,k);

	for(int j=0;j<MAX_LENGTH;j++)
	{
		printf("the %d is:%d\n",j,array[j]);
	}
}