算法（JAVA）—-两道小小课后题

LZ最近翻了翻JAVA版的数据结构与算法，无聊之下将书中的课后题一一给做了一遍，在此给出书中课后题的答案（非标准答案，是LZ的答案，，猿友们可以贡献出自己更快的算法）。

1、编写一个程序解决选择问题。令k=N/2，画出表格显示程序对于N种不同的值的运行时间。

分析：选择问题是指从N个数当中，按升序（降序也可以）排列，找出第k个数。LZ的写法是采用书中给出的算法自己实现的，分别采用冒泡排序和分批处理的方式。以下为LZ写出的算法代码。

import java.util.Arrays;import java.util.Random; Select {Random RANDOM = new Random(47); main(String[] args) {for (int i = 0; i < 10; i++) {printResult(createArray(RANDOM.nextInt(100000)));}}sort(int[] values){for (int i = 1; i < values.length; i++) {for (int j = 0; j < values.length – i; j++) {if (values[j] > values[j + 1]) {int temp = values[j];values[j] = values[j + 1];values[j + 1] = temp;}}}}select(int[] values){if (values == null || values.length == 0) {throw new NullPointerException(“values can’t be null.”);}int k = values.length / 2;int[] temp = Arrays.copyOf(values, k);sort(temp);for (int i = k ; i < values.length; i++) {if (values[i] < temp[k – 1]) {temp[k – 1] = temp[k – 2];for (int j = k – 2; j >0; j–) {if (values[i] > temp[j]) {temp[j + 1] = values[i];break;}else {temp[j] = temp[j – 1];}}}}return temp[k – 1];}[] createArray(int length){int[] values = new int[length];for (int i = 0; i < length; i++) {values[i] = RANDOM.nextInt(length * 2);}return values;}printResult(int[] values){System.out.println(“length:” + values.length);long start = System.currentTimeMillis();System.out.println(“result:” + select(values));System.out.println(“cost:” + (System.currentTimeMillis() – start) + “ms”);System.out.println(“——————————–“);}}明天的希望，让我们忘了今天的痛苦