欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

利用快排寻找数组中第k个最大元素

程序员文章站 2024-03-25 14:52:52
...
/*
 * 利用快排寻找数组中第k个最大元素
 */
public class FindFirstKElement {
	//快排
	public static int getBaseIndex(int[] arr, int start, int end) {
		int base = arr[start];
		while(start < end) {
			while(arr[end] > base && end > start) {
				end --;
			}
			if(end <= start) {
				break;
			}
			else {
				int temp = arr[end];
				arr[end] = arr[start];
				arr[start] = temp;
			}
			while(arr[start] < base && start < end) {
				start ++;
			}
			if(start >= end) {
				break;
			}
			else {
				int temp = arr[start];
				arr[start] = arr[end];
				arr[end] = temp;
			}
		}
		return start;
	}
	
	public static void findFirstKElement(int[] arr, int k, int start, int end) {
		int middle = getBaseIndex(arr, start, end);
		if(middle == k - 1) {
			System.out.println(arr[middle]);
		}
		else if(middle < k - 1) {  //middle右边找
			findFirstKElement(arr, k, middle + 1, end);
		}
		else {	//middle左边找
			findFirstKElement(arr, k, start, middle - 1);
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {23,4,6,8,232};
		int k = 2;
		int start = 0;
		int end = arr.length - 1;
		findFirstKElement(arr, k, start, end);
	}
}

 

相关标签: 快排