寻找数组第二大数和第K大数

一、寻找第二大数

#include "stdio.h"
#include "stdlib.h"

int findsecondmaxvalue(int *a,int size)
{
    int i,max,s_max;
    max=sub_max=-65536; 
    for(i=0;i<size;i++)
    {
        if(a[i]>max)
        {
		s_max=max;  
		max=a[i];
        }
	else if(a[i]<max && a[i]>s_max) //max有可能不持续更新(第一个数就是最大的，只更新了一次)——这样第一个if就无法让s_max 次大值更新了，<span style="font-family: Arial,Helvetica,sans-serif;">为了应付这种情况，用else if来解决——就算你max不更新，我s_max 次大值也要更新</span>
		s_max=a[i];
    }
	return s_max;
}

int main(void)
{
    int x,a[]={111,23,3,5,652,2,3};
    x=findsecondmaxvalue(a,sizeof(a)/sizeof(a[0]));
    printf("这个数组中的次大值为：%dn",x);
    return 0;
}

二、寻找第K大数

可以用快速排序的思路：第一轮排序结束，“中间”的那个数s[i]=x，如果i+1=k，说明恰好s[i]即是第k大数，如果i+1>k，说明第k大数在左半边数组中，则在左边数组进行递归查找。否则在右半边数组中查找。

#include<stdio.h>
int quick_search(int s[],int l,int r,int k);

int quick_search(int s[],int k)
{
    if(r+1 < k)
      return -1;
    if(l < r)
    {
        int i = l,j = r;  //i,j相当于头尾两个指针，相遇时说明把数组/子数组遍历了一遍
        int x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
		j--;  
            if(i < j)    
		s[i++] = s[j];		
            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
		i++;  
            if(i < j) 
		s[j--] = s[i];
        }
        s[i] = x;
        if(i+1==k)
            return s[i];
        else if(i+1>k)
            return quick_search(s,l,i-1,k);   // 递归调用 
        else
            return quick_search(s,i + 1,r,k);
    }
}

int main()
{
	int a[]={66,1,7,4,67,8,27,30};
	int ans=quick_search(a,9,5);
	printf("%dn",ans);
	return 0;
}

参考资料 http://blog.csdn.net/hackbuteer1/article/details/6651804