在数组中找到第k大的元素

给出数组 [9,3,2,4,8]，第三大的元素是 4
给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推

要求时间复杂度为O(n)，空间复杂度为O(1)

public static int kthLargestElement(int k, int[] nums) {
        // write your code here
        if(nums == null || nums.length == 0){
        	return -1;
        }
        int len = nums.length;
        return helper(nums, 0, len - 1, len - k + 1);
        

        
    }
	private static int helper(int[] nums, int l, int r, int k) {
		// TODO Auto-generated method stub
		
		if(l == r){
			return nums[l];
		}
		int position = quitsort(nums, l, r);
		if(position + 1 == k){
			return nums[position];
		}else if(position + 1 < k){
			return helper(nums, position +1 , r, k);
		}else{
			return helper(nums, l, position  - 1, k);
		}
		
		
		
	}
	private static int quitsort(int[] a, int l, int r) {
		// TODO Auto-generated method stub
		int left = l;
		int right = r;
		int key = a[left];
		while(right>left){
             //从后往前比较
             while(right>left&&a[right]>=key)  
                 right--;
             if(a[right]<=key){
                 swap(a, left, right);
             }
             //从前往后比较
             while(right>left&&a[left]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                left++;
             if(a[left]>=key){
                 swap(a, left, right);
             }
         
         }
		return left;
	}
	private static void swap(int[] nums, int left, int right) {
		// TODO Auto-generated method stub
		int temp = nums[left];
		nums[left] = nums[right];
		nums[right] = temp;
		
	}
	 
	
};

对于快速排序，算法复杂度是O(N*logN)。而这个算法的算法复杂度是O(N)。为什么呢？

其实这个地方的算法复杂度分析很有意思。第一次交换，算法复杂度为O(N)，接下来的过程和快速排序不同，快速排序是要继续处理两边的数据，再合并，合并操作的算法复杂度是O(1)，于是总的算法复杂度是O(N*logN)（可以这么理解，每次交换用了N，一共logN次）。但是这里在确定枢纽元的相对位置（在K的左边或者右边）之后不用再对剩下的一半进行处理。也就是说第二次插入的算法复杂度不再是O(N)而是O(N/2)，这不还是一样吗？其实不一样，因为接下来的过程是1+1/2+1/4+........ < 2，换句话说就是一共是O(2N)的算法复杂度也就是O(N)的算法复杂度。

/***************************************************************************** 
 函 数 名  : small_heap_adjust 
 功能描述  : 根据数组构建小顶堆  
 输入参数  : array  待调整的堆数组 
             index  待调整的数组元素的位置 
             length 数组的长度 
 输出参数  : 无 
 返 回 值  : 无  
 修改历史      : 
  1.日    期   : 2012/09/10 
    作    者   : liguangting 
    修改内容   :  
*****************************************************************************/  
void small_heap_adjust(int *array, int index, int length)  
{  
    int child;  
    int temp = array[index];  
      
    if (2 * index + 1 >= length)  
    {  
        return;  
    }  
  
    //子结点位置 = 2 * 父结点位置 + 1  
    child = 2 * index + 1;  
          
    //得到子结点中较小的结点   
    if (child < length - 1 && array[child + 1] < array[child])  
    {  
        ++child;  
    }  
              
    //如果较小的子结点小于父结点那么把较小的子结点往上移动，替换它的父结点   
    if (temp > array[child])  
    {  
        array[index] = array[child];  
    }  
    else  
    {  
        return;  
    }  
          
    //最后把需要调整的元素值放到合适的位置   
    array[child] = temp;  
      
    small_heap_adjust(array, child, length);  
}  
  
/***************************************************************************** 
 函 数 名  : find_kmax_value 
 功能描述  : 查找数组中第K大元素  
 输入参数  : array  待查询的数组  
             length 数组的长度 
             K      第K大  
 输出参数  : 无 
 返 回 值  : 返回第K大元素  
 修改历史      : 
  1.日    期   : 2012/09/10 
    作    者   : liguangting 
    修改内容   :  
*****************************************************************************/  
int find_kmax_value(int *array, int length, int k)  
{  
    int i = 0;  
      
    //把子数组array[0...k-1]构造成小顶堆   
    for (i = k / 2 - 1; i >= 0; i--)  
    {  
        small_heap_adjust(array, i, k);  
    }  
      
    //子数组array[k...length-1]的所有元素与堆顶元素进行比较，若大于堆顶元素  
    //则交换，并重新调整堆   
    for (i = k; i < length; i++)  
    {  
        if (array[i] > array[0])  
        {  
            swap(array[0], array[i]);  
            small_heap_adjust(array, 0, k);  
        }  
    }  
      
    return array[0];  
}  

利用堆排序的思想来查询数组中第K大元素。首先提取子数组array[0...K-1]并构造小顶堆，然后把剩下子数组array[K...N-1]中的所有元素与堆顶元素array[0]进行比较，若大于堆顶元素，则进行交换并重新构造子数组array[0...K-1]使其满足小顶堆的要求。这样的话，最后子数组array[0...K-1]就是N个元素中的前K个最大元素，堆顶array[0]就是N个元素中的第K大元素。

时间复杂度为O(NlogK)，额外空间为O(K)