JAVA寻找最大的K个数

Java #k个数2014-04-16 13:55

第一个解法：快速排序

代码如下

public static void quickSort(int[] arr, int start, int end) {
		if (start < end) {
			int key = arr[start];
			int right = start;
			int left = end;
			while (right < left) {
				while (right < left && arr[left] > key) {
					left --;
				}
				if (right < left) {
					arr[right] = arr[left];
				}
				while (right < left && arr[right] <= key) {
					right ++;
				}
				if (right < left) {
					arr[left] = arr[right];
				}
			}
			arr[right] = key;
			quickSort(arr, start, right-1);
			quickSort(arr, left+1, end);
		}
	}

快速排序之后，数组会是有序的，上面的排序是从小到大的，所以我们输出应该是下面这样

 int k = 4;
		for (int i=arr.length-1; i>=arr.length-k; i--) {
			System.out.println(arr[i]+"  ");
		}

。第一个解法已经好了，但是有没有更好的办法。
答案是有的！我们可以选择部分排序，接下来我们使用选择排序来做解决这个问题。

代码如下：

public static int[] selectSortK(int[] arr, int k) {
		if(arr == null || arr.length == 0) {
			return null;
		}
		int[] newArr = new int[k];
		List<Integer> list = new ArrayList<Integer>();//记录每次最大数的下标
		for (int i=0; i<k; i++) {
			int maxValue = Integer.MIN_VALUE; //最大值
			int maxIndex = i; 
			for (int j=0; j<arr.length; j++) {
				if (arr[j] > maxValue && !list.contains(j) ) {
					maxValue = arr[j];
					maxIndex = j;
				}
			}
			if (!list.contains(maxIndex)) {//如果不存在，就加入
				list.add(maxIndex);
				newArr[i] = maxValue;
			}
		}
		return newArr;
	}

JAVA寻找最大的K个数

相关文章