设计算法 脱颖而出
数字职场
在软件开发中，算法和数据结构是最重要的内容，求职中遇到考算法的题那是司空见惯，特别是大公司，对算法的要求更高，要能根据公司需求写出相应的算法或者帮公司改进现有算法。下面我们以腾讯移动开发的算法考题为例，讲讲如何答题。
题目：有10亿个浮点数，从中找出1万个最大的数，设计一个高性能的算法。
分析：首先，我们需要考虑一下10亿个浮点数，如果都放在内存中，需要40亿byte（约4GB）空间。其次，我们要理解“1万个最大的数”是什么意思——就是把数字从高到低排列，取前1万个数。然后，我们要找出这1万个数，撇开算法优劣，肯定要做的是遍历这10亿个数，通过比较确定答案。最后，我们就知道设计算法的重点就是10亿个浮点数的存储和排序。
题目中规定排序基数是10亿，那么选择时间度为n2的排序就不合理了，冒泡、选择排序都可以否决掉，应该选择时间度为nlog2n的排序：快速排序、堆排序、归并排序。将10亿个浮点数，1千万个数分为一组，拆分成100组，每组进行快速排序，然后将每组的最大的1万个数合并成一个数组，再进行归并排序，最后得出10亿个浮点数中最大的1万个数。这个设计思路考虑了内存不足。开发环境为JDK1.6，Eclipse3.5。
解题步骤
第一步：创建数组，每个数组共有1千万个数，代码如下所示：
float[] arr = new float[10000000]; //初始化1千万长度的数组
for（int i=0;i<10000000;i++）{
arr[i]= rand1.nextFloat（）;//产生一个随机浮点数，赋值给数组中的元素
}
第二步：在每个数组中进行快速排序，按照从低到高的规则将小的数排在前面，大的数排在后面，代码如下所示：
public static float[] sort（float[] nums，int m，int n）{
if（m==n）{
return nums;
}
//以mid为分界点，将小的数排在前面，大的数排在后面
int mid = m;
float midvalue = nums[mid];
int end = n;
while（mid if（nums[end] if（mid==end-1）{ //互换 nums[mid] = nums[end]; nums[end] = midvalue; }else{ //mid前面的移动到end ，end移动到mid ，mid往前移动一个位置 float temp = nums[mid+1]; nums[mid] = nums[end]; nums[mid+1] = midvalue; nums[end] = temp; mid++; } }else{ end——; } } sort（nums，m，mid）; sort（nums，mid+1，n）; return nums; } 第三步：从每个数组中提取排在末位的1万个数，将它们保存到结果数组中，代码如下所示： private static float[] getMax（float arr[]）{ //排序后的数组是升序，所以取值时需倒序 for（int i=arr.length;i>arr.length-10000;i——）{ ret[start]=arr[i-1]; start ++; } return ret; } 第四步：对结果数组进行排序，按照从大到小的顺序从结果数组中提取10000个数，最后输出10000个数即可，代码如下所示: private static void Sort（float arr[]，float temp[]，int m，int n） { if （m == n） return; //拆分成前后两个序列，分别排序 int mid = （m+n）/2; Sort（arr， temp， m， mid）; Sort（arr， temp， mid+1， n）; for （int i = m; i <= n; i++） { temp[i] = arr[i]; } int index1 = m; int index2 = mid + 1; int index = m; //合并已排序的数组 while （index1 <= mid && index2 <= n） { if （temp[index1] < temp[index2]） { arr[index++] = temp[index1++]; } else { arr[index++] = temp[index2++]; } } while（index1 <= mid） { arr[index++] = temp[index1++]; } while（index2 <= n） { arr[index++] = temp[index2++]; } } 在所有的应聘考题中，设计算法的题是比较难的。在答题时，最好将设计流程图画出，这样考官一眼就能看出你的设计思路。 如果时间允许，最好对用快速排序、堆排序、归并排序三种方法设计的优劣进行一个比较，可以让考官眼前一亮。上机时，先看看计算机配置，有4GB以上内存不妨将10亿浮点数放在内存中，否则就要将数据存储到硬盘中。我的建议>>