main.cpp

用三种方法实现在数组中选择第k个最小的元素

#include "stdio.h"
#include <stdlib.h>
#include <TIME.H>


#define MAX_SIZE 10000

int intArray[MAX_SIZE];

void InitArray(int *intArray,int length)             
{	
	int i;

	for(i = 0;i <= length;i++)
		intArray[i] = (int)(rand() * MAX_SIZE / RAND_MAX );
}

void PrintArray(int *intArray,int low,int high)
{	
	int i;

	printf("The Array from %d th to %d th = {  ",low,high);

	for(i = low;i <= high;i++) 
		printf("%d,  ",intArray[i]);

	printf("  }\n");
}

//基于QuickSort的选择算法
/////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////


int Partion(int * L,int low,int high)
{
	//交换数组L中子数组L[low..high]的记录，枢纽记录到位，并返回其所在位置
	//使得此时在他之前的记录均不大于它，在他之后的记录均不小于它

	int pivot;
	int begin = low;

	L[0] = L[low];
	pivot = L[low];
	
	while (low < high)
	{
		while (low < high && L[high] >= pivot) 
			--high;
		L[low] = L[high];
		
		while (low < high && L[low] <= pivot)
			++low;
		L[high] = L[low]; 
	}

	L[low] = L[0];

	return low - begin + 1;
	//return low;
}

/*void QSort(int * L,int low,int high)
{
	//对顺序表L中的子序列L[low,high]作快速排序
	int	pivotLoc ;

	if (low < high)
	{
		pivotLoc = Partion(L,low,high);
		QSort(L,low,pivotLoc - 1);
		QSort(L,pivotLoc + 1,high);
	}
}*/

int Select_QS(int * L,int low,int high,int k)
{
	int pivotLoc;

	if (low < high)
	{
		pivotLoc = Partion(L,low,high);

		if (pivotLoc < k)
		{
			Select_QS(L,pivotLoc + low + 1,high,k - pivotLoc );
		}
		else if (pivotLoc > k)
			Select_QS(L,low,pivotLoc + low -1,k);
		else  //pivotLoc == k
			//return L[pivotLoc];
			return L[pivotLoc + low - 1];
	}
			
}

///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////


//基于堆排序的选择算法
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////

void Swap(int * x,int * y)
{
	int temp;

	temp = *x;
	*x = *y;
	*y = temp;
}

void HeapAdjust(int * H,int s,int m)
{
	//已知H中除H[s]外均满足小顶堆的定义，本函数调整H[s]，使H[s..m]成为一个小顶堆

	int	rc;
	int j;

	rc = H[s];

	for (j = 2 * s;j <= m;j *= 2)
	{
		if (j < m && H[j] > H[j + 1])
			++j;
		if (rc < H[j])
			break;
		
		H[s] = H[j];
		s = j;
	}
	H[s] = rc;
}

int HeapSort(int *H,int length,int k)
{
	int i;


	for (i = length / 2;i > 0;--i)
	{
		HeapAdjust(H,i,length);
	}

	for (i = length;i > 1;--i)
	{
		Swap(&(H[1]),&(H[i]));

		HeapAdjust(H,1,i - 1);
	}
    
	return H[length - k + 1];

}

int Select_HS(int *H,int length,int k)
{
	int i;

	for (i = length / 2;i > 0;--i)
	{
		HeapAdjust(H,i,length);
	}

	for (i = length;i > (length - k + 1);--i)
	{
		Swap(&(H[1]),&(H[i]));

		HeapAdjust(H,1,i - 1);
	}

	return H[1];
}

///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
	int value = 0;
	int	k = 7;
	long i;
	clock_t begin,end;
	double duration;

	FILE * file1;
	FILE * file2;

	file1 = fopen("Select_QS.txt","wr+");
	file2 = fopen("Select_HS.txt","wr+");

	for (i = 1000; i < MAX_SIZE;i += 100)
		for (k = 7;k < MAX_SIZE / 100;k += 5)
		{
			InitArray(intArray,i);
			
			//测量基于QuickSort的选择算法的性能
			////////////////////////////////////////////////////////////////////////////////

			begin=clock();

			value = Select_QS(intArray,1,i,k);

			end=clock();

			duration=(double)(end-begin) ;

			printf("The %d th element in Array[1,%d] by Select_QS is :  %d\n",k,i,value);

			fprintf(file1,"%d		%d		%f\n",i,k,duration);
			
			////////////////////////////////////////////////////////////////////////////////

			
			//测量基于HeapSort的选择算法的性能
			////////////////////////////////////////////////////////////////////////////////
			begin=clock();

			value = Select_HS(intArray,i,k);
			
			end=clock();

			duration=1.0 * (end-begin) / CLOCKS_PER_SEC;

			printf("The %d th element in Array[1,%d] by Select_HS is :  %d\n",k,i,value);
			
			fprintf(file2,"%d		%d		%f\n",i,k,duration);
			///////////////////////////////////////////////////////////////////////////////
			
			
			//用HeapSort进行“三模冗余”正确性验证
			///////////////////////////////////////////////////////////////////////////////
			value = HeapSort(intArray,i,k);
			
			printf("The %d th element in Array[1,%d] by HeapSort is :  %d\n",k,i,value);
			///////////////////////////////////////////////////////////////////////////////
		}
	return 0;
}