求解数组中的第k个最大元素

1.插入法

整体思路如下：建立一个数组长度为k的数组orderArray，把原数组array中最左侧的k个元素放入orderArray，对orderArray排序，接着从k开始遍历原数组array，与orderArray的最后一个元素比较，即orderArray[k-1]，如果比orderArray[k-1]大，说明应插入到orderArray中。接着拿这个比orderArray[k-1]大的元素和orderArray中的元素一一比较，确定插入位置，最后将元素插入。

代码如下：

    /**
	 * 插入法
	 * @param array
	 * @param kth
	 * @return
	 */
	public static int kthBig(int[] array, int kth) {
		int[] orderArray = new int[kth];
		for(int i = 0; i < kth; i ++) {
			orderArray[i] = array[i];
		}
		//给orderArray排序
		for(int i = 0; i < orderArray.length; i ++) {
			for(int j = 0; j < orderArray.length - i -1; j ++) {
				if(orderArray[j] < orderArray[j + 1]) {
					int temp = orderArray[j];
					orderArray[j] = orderArray[j+1];
					orderArray[j+1] = temp;
				}
			}
		}
		//遍历array数组中从kth开始的元素，和orderArray的最后一个元素比较，由于orderArray已经有序，所以如果array中的元素比orderArray中的最后一个大，
		//说明要向左边插入，接着依次和orderArray中的元素比较，
		for(int i = kth; i < array.length; i ++) {
			if(orderArray[kth-1] < array[i]) {
				//类似插入排序
				//先插入，排序数组左侧已经有序，让最后插入的元素依次和左侧比较
				//上面if已经判断过比orderArray中的最后一个大，所以j从kth-2开始
				int v = array[i];
				int j = kth-2;
				for(; j >=0; j --) {
					//元素右移
					if(v > orderArray[j]) {
						orderArray[j+1] = orderArray[j];
					} else {
						//比orderArray[j]小的时候，退出循环，表明找到了插入的位置，即j+1
						break;
					} 
				}
				orderArray[j+1] = v;
			}
		}
		return orderArray[kth-1];
	}

2.最小堆法

整体思路如下：维护一个容量为k的最小堆，堆中元素代表数组中最大的k个元素，由于是最小堆，堆顶即为第k个最大元素。

在原数组上通过移动元素构建k个元素的最小堆，这样不用开辟额外的内存空间，空间复杂度为O(1)。

代码如下：

    /**
	 * 最小堆法，以k个元素构建一个最小堆，本身是数组，所以在原数组中调整顺序，即可构造一个长度为k的最小堆，堆顶即为第k个最大元素
	 * 这样不用开辟额外空间，空间复杂度为O(1)
	 * @param array
	 * @param k
	 * @return
	 */
	public static int findKthLargestNumber(int array[], int k) {
		buildHeap(array, k);
		for(int i = k; i < array.length; i ++) {
			if(array[i] > array[0]) {
				array[0] = array[i];
				downAdjust(array, 0, k);
			}
		}
		//最小堆，返回堆顶元素
		return array[0];
	}
	
	/**
	 * 
	 * @param array 待调整的堆
	 * @param length 堆的有效大小
	 */
	private static void buildHeap(int[] array, int length) {
		for(int i = (array.length-2)/2; i >= 0; i --) {
			downAdjust(array,i,length);
		}
	}
	/**
	 * 
	 * @param array 待调整堆
	 * @param i 待调整的非叶子节点索引
	 * @param length 堆的有效长度
	 */
	private static void downAdjust(int[] array, int i, int length) {
		int temp = array[i];
		int childIndex = 2*i+1;
		
		//递归
		//索引值不能大于长度值
		while(childIndex < length) {
			//存在右节点，且右节点的值小于左节点，则定位到右节点，即右节点的值较小，然后拿右节点的值和父节点值比较，小于父节点，则父节点下沉，右节点上浮到父节点
			if(childIndex+1<length && array[childIndex] > array[childIndex+1]) {
				childIndex ++;
			}
			//子节点的值比父节点大，直接退出，因为是最小堆，所以不用调整
			if(array[childIndex] >= temp) {
				break;
			}
			//单项赋值
			array[i] = array[childIndex];
			//向下递归
			//以上面定位到的叶子节点作为下一轮的父节点，重新赋值叶子节点的索引，开启下一轮循环
			i = childIndex;
			childIndex = 2*i+1;
		}
		array[childIndex] = temp;
	}

3.分治法

整体思路如下：和快速排序类似，这里采用“单边法实现”，以首个元素为基准，遍历数组array，比基准大的，放左边，比基准小的放右边，将原数组以基准分割成两部分，基准左侧的元素个数比k多，则在左侧区域继续分治，比k少，则在右侧继续分治。当元素个数和k相等时，array[k-1]即为数组中第k大个元素。

代码如下：

    /**
	 * 分治法，左侧较大区域，右侧较小区域
	 * @param array
	 * @param k
	 * @return
	 */
	public static int findKthLargestNumber2(int[] array, int k, int start, int end) {
			
			int pivotIndex = start;
			int pivot = array[pivotIndex];
			int mark = start;
			int result;
			
			for(int i = start+1; i <= end; i ++) {
				if(array[i] > pivot) {
					mark ++;
					int temp = array[i];
					array[i] = array[mark];
					array[mark] = temp;
				}
			}
			array[pivotIndex] = array[mark];
			array[mark] = pivot;
			
			if(mark == k - 1) {
				return array[mark];
			}
			if(mark > k - 1) {
				result = findKthLargestNumber2(array, k, start, mark-1);
			} else {
				result = findKthLargestNumber2(array, k, mark+1, end);
			}
			return result;
	}

参考：漫画算法1&2