【100题】第五题

查找最小的k个元素（数组）
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

一，最原始的一种方法

插入排序，后输出最小的k个

源码：

#include "stdio.h"
/*寻找最小的k个数方法*/
void min(int a[],int n,int k)
{
	int temp;
	for(int i=1;i<n;i++) //插入排序 
	{
		for(int j=0;j<i;j++)
		   {
		   	   if(a[j]>a[i])
		   	   {
   	   			  temp=a[j];
   	   			  a[j]=a[i];
   	   			  a[i]=temp;
   	   	    	}
   			
   	    	}
	}
	
	
	
} 

int main()
{
    int a[10]={2,1,3,4,5,7,6,8,9};//数组 
    int k=5;//输出最小的5个
    min(a,9,k);
 
}

缺点：时间复杂度高。O(n^2);

二，简单优化后

排序方法使用快速排序

<span style="font-size: 13px;">int Partition(int a[],int i,int j)
{
	int temp=a[i];//记录下轴的位置 
	while(i<j)
	{
	    while(i<j&&temp<=a[j])//将比轴小的  移动到低端 
		   j--;
     
            a[i]=a[j];//小的 等于后面的大的 (之后的i 会增加)【后面的大的 移动到前面来后 本趟不会再动】 
                
            while(i<j&&temp>=a[j])//将比轴大的 移动到高端 【从前往后找 ，找到 小的往后移动】 
                 i++;
        
            a[j]=a[i]; // a[j] 存的 上面找到的小的 （在这里改变）小的等于 前面大的 【】 
          
	}
	a[i]=temp;//轴的位置 
	
	return i;		
}
void Quicksort(int a[],int i,int j)//快速排序 
{
	int p;
	if(i<j)
	{
		 
	    p=Partition(a,i,j);	    
		Quicksort(a,i,p-1);
		Quicksort(a,p+1,j);
	}
}</span>

分析：虽然时间提高了，但是还是可以再优化。O(nlogn)

三，再次优化

维护一个K大小的数组，只用遍历一次n个元素，然后就能得到最小的k个元素。

伪代码：

1， 将n个元素前k个放入数组中，每插入一个元素，对k数组中元素进行插入排序；

2，从第k+1开始，每遍历一个元素，跟数组中最大的（maxK）比较 maxK>a则将maxK删除，将a插入k中。直到程序结尾。

源码：

<strong>void  getMink_by_array(int a[],int n,int k)//通过维护k个数组 得到最小的k个元素 
{
	int min[k];//从小到大排序 
	int i,j,temp,l;
	min[0]=a[0];
	//printf("%3d",min[0]);
	for(i=1;i<k;i++) //插入排序维护一个从小到大的数组 
	{
		min[i]=a[i];
		for(j=0;j<i;j++) 
		  {
		     if(min[i]<min[j])
		     {
     			temp=min[j];
     			min[j]=min[i];
     			min[i]=temp;
     		 }
		  }
	}
	
  	for(l=k;l<n;l++)
	{
		if(a[l]<min[k-1])
		{
			min[k-1]=a[l];
   			for(j=0;j<k;j++) 
		    {
		     	if(min[k-1]<min[j])
		        {
     				temp=min[j];
     				min[j]=min[k-1];
     				min[k-1]=temp;
     		    }
		    }
			
		}
	}</strong> 
	

五，还能优化，将维护一个k大小数组换成维护一个k大小堆

void HeapAdjust(int array[],int i,int nLength)//调整堆 
{
	int nChild;
	int nTemp;//赋值为待调整的 节点
	 //从应该调整的节点开始 ，直到该节点 已经没有孩子节点 
	for(nTemp=array[i];nLength>2*i+1;i=nChild)//由于根节点从0开始计数 故左孩子 为2*i+1  
	{
		nChild=2*i+1;//子节点=2（父节点）+1 
			
		/*一共两个子节点的话得到 较大的一个*/
		  //nChild<nLength-1 判断到头没有 
		if(nChild<nLength-1&&array[nChild+1]>array[nChild])
		      ++nChild;
		   
		    /*如果较大子节点大于父节点  将子节点 调整到父节点*/
			if(nTemp<array[nChild])
			  array[i]=array[nChild];
		    else
		      break;//这个地方不加 会出错  第一个会输出第二个 
		      
      array[nChild]=nTemp;//子节点 等于父节点 
	} 
}
void HeapSort(int a[],int length)
{
	/*初建堆 */
	for(int i=length/2-1;i>=0;--i)//从最后一个 非叶子节点调整 （这里的  i是下标） 
	   HeapAdjust(a,i,length);
   
    int temp;
    for(int i=length-1;i>0;--i)//将堆顶放最后 ，然后对剩余的元素对调整 
       {
       	/*第一个最大元素跟最后一个交换*/
       	  temp=a[0];
       	  a[0]=a[i];
       	  a[i]=temp;
       	  
       	  HeapAdjust(a,0,i);//调整堆 (注意 length=i  由于堆是逐渐变小的)
       }
	
}
void  getMink_by_heap(int a[],int n,int k)//通过维护k个数组 得到最小的k个元素 
{
	int min[k];//从小到大排序 
	int i,j,temp,l;
	
	
	for(i=0;i<k;i++) //插入排序维护一个从小到大的数组 
	{
		min[i]=a[i];
	}
	 HeapSort(min,k);//堆排序
		 	
  	for(l=k;l<n;l++)
	{
		if(a[l]<min[k-1])
		{
			min[k-1]=a[l];//让小于k堆中最大元素的 a[l] 跟 min[k-1]交换 
   			HeapAdjust(min,0,k-1);	
		}
	} 
	
	for(i=0;i<k;i++)
	   printf("%3d",min[i]);
}

六，最后四种方法综合代码如下

#include "stdio.h"
/*寻找最小的k个数方法*/
void min(int a[],int n,int k)
{
	int temp;
	for(int i=1;i<n;i++) //插入排序 
	{
		for(int j=0;j<i;j++)
		   {
		   	   if(a[j]>a[i])
		   	   {
   	   			  temp=a[j];
   	   			  a[j]=a[i];
   	   			  a[i]=temp;
   	   	    	}
   			
   	    	}
	}
	for(int i=0;i<k;i++)
       printf("%3d",a[i]);	
} 

int Partition(int a[],int i,int j)
{
	int temp=a[i];//记录下轴的位置 
	while(i<j)
	{
		while(i<j&&temp<=a[j])//将比轴小的  移动到低端 
		   j--;
     
          a[i]=a[j];//小的 等于后面的大的 (之后的i 会增加)【后面的大的 移动到前面来后 本趟不会再动】 
       
          
        while(i<j&&temp>=a[j])//将比轴大的 移动到高端 【从前往后找 ，找到 小的往后移动】 
           i++;
        
        a[j]=a[i]; // a[j] 存的 上面找到的小的 （在这里改变）小的等于 前面大的 【】 
        
 	  
	}
	a[i]=temp;//轴的位置 
	
	return i;		
}

void Quicksort(int a[],int i,int j)//快速排序 
{
	int p;
	if(i<j)
	{
		 
	    p=Partition(a,i,j);	    
		Quicksort(a,i,p-1);
		Quicksort(a,p+1,j);
	}
}

void  getMink_by_array(int a[],int n,int k)//通过维护k个数组 得到最小的k个元素 
{
	int min[k];//从小到大排序 
	int i,j,temp,l;
	min[0]=a[0];
	//printf("%3d",min[0]);
	for(i=1;i<k;i++) //插入排序维护一个从小到大的数组 
	{
		min[i]=a[i];
		for(j=0;j<i;j++) 
		  {
		     if(min[i]<min[j])
		     {
     			temp=min[j];
     			min[j]=min[i];
     			min[i]=temp;
     		 }
		  }
	}
	
  	for(l=k;l<n;l++)
	{
		if(a[l]<min[k-1])
		{
			min[k-1]=a[l];
   			for(j=0;j<k;j++) 
		    {
		     	if(min[k-1]<min[j])
		        {
     				temp=min[j];
     				min[j]=min[k-1];
     				min[k-1]=temp;
     		    }
		    }
			
		}
	} 
	
	for(i=0;i<k;i++)
	   printf("%3d",min[i]);
}
void HeapAdjust(int array[],int i,int nLength)//调整堆 
{
	int nChild;
	int nTemp;//赋值为待调整的 节点
	 //从应该调整的节点开始 ，直到该节点 已经没有孩子节点 
	for(nTemp=array[i];nLength>2*i+1;i=nChild)//由于根节点从0开始计数 故左孩子 为2*i+1  
	{
		nChild=2*i+1;//子节点=2（父节点）+1 
			
		/*一共两个子节点的话得到 较大的一个*/
		  //nChild<nLength-1 判断到头没有 
		if(nChild<nLength-1&&array[nChild+1]>array[nChild])
		      ++nChild;
		   
		    /*如果较大子节点大于父节点  将子节点 调整到父节点*/
			if(nTemp<array[nChild])
			  array[i]=array[nChild];
		    else
		      break;//这个地方不加 会出错  第一个会输出第二个 
		      
      array[nChild]=nTemp;//子节点 等于父节点 
	} 
}
void HeapSort(int a[],int length)
{
	/*初建堆 */
	for(int i=length/2-1;i>=0;--i)//从最后一个 非叶子节点调整 （这里的  i是下标） 
	   HeapAdjust(a,i,length);
   
    int temp;
    for(int i=length-1;i>0;--i)//将堆顶放最后 ，然后对剩余的元素对调整 
       {
       	/*第一个最大元素跟最后一个交换*/
       	  temp=a[0];
       	  a[0]=a[i];
       	  a[i]=temp;
       	  
       	  HeapAdjust(a,0,i);//调整堆 (注意 length=i  由于堆是逐渐变小的)
       }
	
}
void  getMink_by_heap(int a[],int n,int k)//通过维护k个数组 得到最小的k个元素 
{
	int min[k];//从小到大排序 
	int i,j,temp,l;
	
	
	for(i=0;i<k;i++) //插入排序维护一个从小到大的数组 
	{
		min[i]=a[i];
	}
	 HeapSort(min,k);//堆排序
		 	
  	for(l=k;l<n;l++)
	{
		if(a[l]<min[k-1])
		{
			min[k-1]=a[l];//让小于k堆中最大元素的 a[l] 跟 min[k-1]交换 
   			HeapAdjust(min,0,k-1);	
		}
	} 
	
	for(i=0;i<k;i++)
	   printf("%3d",min[i]);
}

int main()
{
	int a[10]={2,1,3,4,5,7,6,8,9};//数组 
	int k=5;//输出最小的5个
	
    printf("********************\n");
    printf("1,插入排序后，获得k个最小数\n");
    printf("2,快速排序后，获得k个最小数\n"); 
    printf("3,维护一个k大小数组，获得k个最小数\n");
	printf("4,维护一个k大小堆，获得k个最小数\n");
    printf("********************\n");
	 
    int i;
    
    while(1)
    {
	    scanf("%d",&i);    
    	switch(i)
    	{
    		case 1:min(a,9,k);
                   printf("\n执行完毕请继续……\n");break;
    		case 2:Quicksort(a,0,8);
	               for(int i=0;i<k;i++)
	                   printf("%3d",a[i]);
				   printf("\n执行完毕请继续……\n"); break;
    		case 3:getMink_by_array(a,9,k);
			       printf("\n执行完毕请继续……\n"); break;
    		case 4:getMink_by_heap(a,9,k);
                   printf("\n执行完毕请继续……\n");break;
    		case 5:break;
    		case 6:break;
    		case 7:break;
    		case 8:break;
    		case 9:break; 		
    	
   	    }
    	
    }
}