在前一篇讲选择数问题时，使用了一种类似于快速排序的算法来解决选择数问题，见:http://www.iflym.com/index.php/code/201108240001.html。
而根据算法导论上的一种最坏时间为O(n)的一种解法，其详细的步骤如下所示：
- 将数组s按5个为一组，划分成不同的小组,小组数
- 对每个小组，进行插入排序，并选择其中的中位数
- 将每个小组的中位数，组成一个新的数组，并递归的选择出最终的中位数m
- 以m作为参照数，将数组s划分成两个部分，使得m所处的位置数比左侧的数目大1
- 如果左侧的数目数恰好为寻找的第k位数，则m即为我们要找的数，否则继续在左侧或者右侧进行查找
有了几个的思路，具体算法就很简单了。参考代码如下所示：
private static int find2(int[] ints, int k, int start, int end) {
//如果k为1,则寻找最小数，如果k为end-start+1则寻找最大数
//总长度小于5,直接插入排序并查找
......
//寻找到中位数
int z = findMiddle(ints, start, end);
//按中位数分割数组，其中ints[divide]=z
int divide = divide(ints, z, start, end);
//判断在哪个部分
int frontNum = divide - start;
//恰好为中位数
if(frontNum == k - 1)
return ints[divide];
//高部分
if(frontNum < k)
return find2(ints, (k - frontNum), divide + 1, end);
//低部分
return find2(ints, k, start, divide - 1);
}
中间有几个函数值得注意，首先即是寻找中位数的算法，代码如下所示:
/** 寻找中位数 */
private static int findMiddle(int[] ints, int start, int end) {
//按5进行分组
int sum = end - start + 1;
if(sum <= 5) {
charuSort(ints, start, end);
return ints[start + calcMiddleSum(start, end)];
}
int z = sum / 5;
z = sum % 5 == 0 ? z : z + 1;
//另开数组用于存储每组的中位数
int[] aints = new int[z];
//每组插入排序
for(int i = 0;i < z;i++) {
int zStart = i * 5;
if(i == z - 1) {
charuSort(ints, zStart, end);
aints[i] = ints[zStart + calcMiddleSum(end, zStart)];
} else {
charuSort(ints, zStart, zStart + 5);
aints[i] = ints[zStart + 2];
}
}
return findMiddle(aints, 0, z - 1);
}
以上即为算法为O(n)的算法参考实现，当然本实现的未必是最优的，也可能达不到《算法导论》中O(N)的运行效率，仅给一个实现参考。
本实现，支持数组中重复的数字，这是在《算法导论》中被回避的一节（文中假设所有数都不相同）。
转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/code/201110120001.html