学步园

问题描述：有很多个无序的数，我们姑且假定它们各不相同，如何选出其中最大的若干数？

可能有人会说先排序后查找下就不ok了吗？其实如果是大数据的话，内存有限，这样排序是没法运行的，还有时间复杂度也挺高的

我觉得下面2个算法挺好的

算法一、回忆下快速排序，快排中的每一步，假设数组下标从start---->end,选个pivot element 主元，经过一次partition ,pivot element位于正确的位置q，比q下标小的元素比arr[q]大，比q下标大的元素值比arr[q]下，根据快排的思想，若干此时从起始位置到q还有k个元素，你很幸运找到你所要想的k个元素了，如果小于k个元素，你在[q+1...end]中找k-(q-start+1)，否则，到[start...q-1]找k个

// k个大数.cpp : 定义控制台应用程序的入口点。
//author:songzhengchao
//实现查找k个大元素

#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int qsort(int arr[],int start,int end)//0...n
{
	int i=start-1;//start---i >=x
	int j=start;//i+1----j <x
	int change;
	srand((unsigned)time(NULL));
	int e=rand()%(end-start+1)+start;
	
	//swap(&arr[e],&arr[end]);
	change=arr[e];
	arr[e]=arr[end];
	arr[end]=change;
	int tmp=arr[end];
	
	for(;j<end;j++)
	{
		if(arr[j]>=tmp)
		{
			//swap(arr[i+1],arr[j]);
			change=arr[i+1];
			arr[i+1]=arr[j];
			arr[j]=change;
			i++;
		}
	}
	//swap(arr[end],arr[i+1]);
	change=arr[end];
	arr[end]=arr[i+1];
	arr[i+1]=change;
	return i+1;

	
}
void quick_sort(int arr[],int start,int end,int k)//k个  start...k-1+start
{
	if(start<end)
	{
		int q=qsort(arr,start,end);//q作为放置x的正确位置
		int i;
		int number=q-start+1;
		if(number==k)
		{
			for(i=start;i<=q;i++)
			{
				cout<<arr[i]<<"  ";
			}
		}else if(number>k)
		{
			quick_sort(arr,start,q-1,k);
		}else
		{
			quick_sort(arr,q+1,end,number-k);
		}
	}
}
		
		

时间复杂度为N*log(2,k)

个人觉得第一次还是要吧N个排序，内存的要求没有考虑，但排序的次数减少了

解法二、开始建k个元素的最小堆，从k+1元素开始遍历元素x，如果比heap[0]小的话，跳过，否认heap[0]=x,调整堆的结构

void build_heap(double arr[],int n,double x)//建最小堆
{
	arr[n]=x;
	double tmp=x;
	while(n>0)
	{
		if(arr[n/2]>tmp) arr[n]=arr[n/2];
		n/=2;
		
	}
	if(n>=0)
		arr[n]=tmp;
	
}
void delete_heap_1(double arr[],double x)//调整从堆顶元素
{
	
	int j;
	double tmp=arr[0];
	double t;
	arr[0]=x;
	int i=0;
	while(i<K)//还有孩子
	{
		j=2*i+1;
		if(j>=K) break;
		if((arr[j]>arr[j+1])&&(j+1<K)) j=j+1;
		if(arr[j]>=arr[i]) break;
		else
		{
			t=arr[j];
			arr[j]=arr[i];
			arr[i]=t;
			i=j;
		}
	}
	

	
}

上面的代码只是简单的测试下算法，最好能用模板，提高程序的可用性