输出前m大的数java_第K大数 算法分析、设计与实现（Java）

问题描述：有一个大小为n的数组A[0,1,2,…,n-1]，求其中第k大的数。

策略：

(1)   判断问题的性质，是排序型？最优型？其他？

(2)   根据不同类型的问题挑选不同的算法。“已知算法->递归->分治->贪心->回溯法->分支限界法->动态规划->算法设计”

(3)   根据相应的算法进行分析

目录

0，分析输入输出

这个问题并不限制输入输出，既可以是网络环境，也可以是其他环境。

网络环境下一般采用的都是流式算法，其他环境一般都是数据齐全的。

故可以将该问题的输入输出分为两大类：流型，稳定型

1，分析算法

该问题并不是最优型，不是那种求最优值、最优解的问题(如：揹包问题)。而是排序型

(1)先从稳定型的入手：

看到球第K大数这个标题，第一想法就是：排序

①     完全排序：

一上来先给这堆数据来个排序，什么排序都行，只要够快，然后直接从数据中取第K大的就可以了。

A完全排序

B输出第K大数

②     不完全排序：

对于不重复使用的数据来说，完全排序太过于浪费，一般只需要排到第K个数。这里可以使用冒泡排序

A使用冒泡排序

B循环K次

C输出第K大数

③     分治：

按照上面的想法，既然第K大数后面的数没有用，那么也有可能第K大数前面的数也没什么用。只需要找出第K大数就可以了，于是可以用快速分治来取得第K大数。这种思想类似于二分法

A通过快速排序，选择数X，进行一轮降序排序

B判断X的位置是否刚好是第K位，若是则直接输出；否则执行C

C若X的位置大于K，则选择[0,X)进行下一轮排序；否则取得(X,n]进行下一轮

D若找到第K大数则直接输出

(2)流型：

网络环境下，数据的长度是不稳定的，如果K不是很大的话，可以创建一个大小为K的数组，将数据往里套，超出范围的数据直接抛弃。第K个位置的数据即为第K大数

A创建大小为K的数组，每个元素都赋值为整数最小值，以保证数据能正常进行判断

B每当有数据时，将数据插入到数组中，维持有序。

C当需要输出第K大数时，直接输出第K位置的数据。

2，时间复杂度与空间复杂度

(1)   在有序的情况下选取第K大数

①  完全排序：O(n*logn),内存占用n，适合反复求取同一组数的第XX大数的情况。但k>logn

②  不完全排序：O(n*k),内存占用n，适合反复求取同一组数的第XX大数的情况。但k

(2)   在无序的情况下选取第K大数

①  流型：O(n*k),内存占用k，适合网络流式的第XX大数计算，计算完后不保存N个数

②  分治型：O(n),内存占用n

3，测试结果

选取随机数范围：0~10000。数组中数的个数N，测试次数M，目标K

N

M

K

完全排序

不完全排序

流型

分治型

20

10000

10

66

7

12

19

100

10000

10

94

25

19

26

1000

10000

10

1053

224

46

69

1000

10000

800

1014

15536

2407

122

10000

10000

800

14267

不计算

10348

1470

1000

100000

800

9584

不计算

25189

581

显然：在N<1000且M、K较小时，更适合使用流型。

但随着运算次数，运算数量级的增加，流型将会大量占用分配内存，导致明显的速度的下降。(这是在本机上会出现问题，因为涉及到不断地资源分配，但在网络环境下只会用到一个大小为K的数组)

分治型的表现最为优秀，无论是数量级的增加，还是计算次数的增加，都能很好保证较优的计算效率。

完全排序则更适合反复求第XX大(小)的情况。例如：数据库

4，代码

package divideAndConquer;

import java.util.Date;

import java.util.Random;

/**

* 输入N个数，输出第K大数

* @Input N K N个数

* @Output第K大数

*

*/

public class FindK {

public static void main(String[] args) {

Random random = new Random(newDate().getTime());

int N = 1000; // 待查询数组

int MAX = 10000; //

int K = 800; // 目标数

int[] nums = new int[N];

for (int i = 0; i < N; i++) {

nums[i] = random.nextInt(MAX);

}

// System.out.print("处理前：" + Arrays.toString(nums));

System.out.println();

System.out.println();

int M = 100000;

/* 有序 */

// 完全排序

// System.out.println("完全排序:" + findKBySort(nums.clone(), K));

long t1 = System.currentTimeMillis();

for (int i = 0; i < M; i++) {

findKBySort(nums.clone(), K);

}

long t2 = System.currentTimeMillis();

System.out.println("耗时：" + (t2 - t1));

// 不完全排序

// System.out.println("不完全排序:" + findKByBubbleSort(nums.clone(), K));

t1 = System.currentTimeMillis();

for (int i = 0; i < M; i++) {

findKByBubbleSort(nums.clone(), K);

}

t2 = System.currentTimeMillis();

System.out.println("耗时：" + (t2 - t1));

/* 无序 */

// 插入法

// System.out.println("插入法:" + findKByArray(nums.clone(), K));

t1 = System.currentTimeMillis();

for (int i = 0; i < M; i++) {

findKByArray(nums.clone(), K);

}

t2 = System.currentTimeMillis();

System.out.println("耗时：" + (t2 - t1));

// 快速分治

// System.out.println("快速分治:"

// + findKByDivAndConq(nums.clone(), 0, nums.length - 1, K));

t1 = System.currentTimeMillis();

for (int i = 0; i < M; i++) {

findKByDivAndConq(nums.clone(), 0, nums.length - 1, K);

}

t2 = System.currentTimeMillis();

System.out.println("耗时：" + (t2 - t1));

}

/**

* 先排序，后取得第K大数

*/

public static int findKBySort(int[] nums, int K) {

quickSort(nums, 0, nums.length - 1, false);// 降序排序

return nums[K - 1];

}

/**

* 快速排序:

*

* @param nums 整型数组

* @param orient true则升序，false则降序

*/

public static void quickSort(int[] nums, int fromIndex, int toIndex,

boolean orient) {

if (nums == null || fromIndex >= toIndex)

return;

int temp = 0;

int mid = (fromIndex + toIndex) / 2;

int midNum = nums[mid];

int a = fromIndex, b = toIndex;

while (a < b) {

if (orient) {

while (nums[a] <= midNum && a < mid) {

a++;

}

while (nums[b] >= midNum && b > mid) {

b--;

}

} else {

while (nums[a] >= midNum && a < mid) {

a++;

}

while (nums[b] <= midNum && b > mid) {

b--;

}

}

if (a == mid) {

mid = b;

} else if (b == mid) {

mid = a;

}

temp = nums[a];

nums[a] = nums[b];

nums[b] = temp;

}

quickSort(nums, fromIndex, mid - 1, orient);

quickSort(nums, mid + 1, toIndex, orient);

}

/**

* 冒泡排序取得第K大数，只需循环K次，取得前K个数即可

*/

public static int findKByBubbleSort(int[] nums, int K) {

int temp = 0;

for (int i = 0; i < K; i++) {

for (int j = nums.length - 1; j > i; j--) {

if (nums[j - 1] < nums[j]) {

temp = nums[j - 1];

nums[j - 1] = nums[j];

nums[j] = temp;

}

}

}

return nums[K - 1];

}

/**

* 创建大小为K的数组，并不断将数据有序插入数组中，最后取得第K个数

*/

public static int findKByArray(int[] nums, int K) {

int[] array = new int[K];// 创建大小为K的数组

// 将数据有序插入数组

int count = 1;// array 中有效数的个数

int index = 0;

array[0] = nums[0];

for (int i = 1; i < nums.length; i++) {

if (nums[i] >= array[count - 1]) {//

if (count < K) {

array[count] = array[count - 1];

}

index = count - 2;

while (index >= 0&& nums[i] >= array[index]) {// 数组后移一位

array[index + 1] = array[index];

index--;

}

array[index + 1] = nums[i];// 插入

if (count < K) {//

count++;

}

} else {

if (count < K) {

array[count] = nums[i];

count++;

}

}

}

return array[K - 1];

}

/**

* 快速分治法，求第K大数。根据一个数，将数组中所有数进行快速排序，使得该数下标前的数大于该数，下标后的数小于该数

*/

public static int findKByDivAndConq(int[] nums, int fromIndex, int toIndex,

int K) {

int a = fromIndex, b = toIndex;

int midIndex = a;

while (a < b) {

while (a < b && nums[b] <= nums[midIndex]) {

b--;

}

swap(nums, midIndex, b);

midIndex = b;

while (a < b && nums[a] >= nums[midIndex]) {

a++;

}

swap(nums, midIndex, a);

midIndex = a;

}

if (midIndex > K - 1) {

return findKByDivAndConq(nums, fromIndex, midIndex - 1, K);

} else if (midIndex < K - 1) {

return findKByDivAndConq(nums, midIndex + 1, toIndex, K);

} else {

return nums[midIndex];

}

}

/**

* 交换

*

*/

public static void swap(int[] nums, int a, int b) {

int temp = nums[a];

nums[a] = nums[b];

nums[b] = temp;

}

}

总结：在本机上或许分治型的更为合适，这是因为数据的齐全的，但在网络环境下流型的更为合适。网络环境下的数据虽然不断增加，但是一直都使用着同一个大小为K的数组