学步园

　　在软件开发中，算法和数据结构是最重要的内容，求职中遇到考算法的题那是司空见惯，特别是大公司，对算法的要求更是高，要能根据公司需求写出相应的德算法或者帮助公司改进现有算法。下面是腾讯移动开发的算法考题。

　　题目：有10亿个浮点数，从中找出1万个最大的数，设计一个高性能的算法。

　　分析：首先，我们需要考虑一下10亿个浮点数，如果都放在内存中，需要40亿byte（约4GB）空间。其次，我们要理解“1万个最大的数”是什么意思-就是把数字从高到低排列，取前1万个数。然后，我们要找出这1万个数，撇开算法优劣，肯定要做的是遍历这10亿个数，通过比较确定答案。最后，我们就知道设计算法的重点就是10亿个浮点数的存储和排序。

　　题目中规定排序基数是10亿，那么选择时间度为n²的排序就不合理了，冒泡、选择排序都可以否决掉，应该选择时间度为nlog₂n的排序：快速排序、堆排序、归并排序。将10亿个浮点数，1千万个数分为一组，拆分成100组，每组进行快速排序，然后将每组的最大1万个数合并成一个数组，再进行归并排序，最后得出10亿个浮点数中最大的1万个数。这个设计思路考虑了内存不足。开发坏境为JDK6，Eclipse3.5。

解题步骤

　　第一步：创建数组，每个数组共有1千万个数，代码如下所示：

float[] arr = new float[10000000];  //初始化1千万长度的数组
for(int i = 0; i < 1000000; 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 < end){
    if(nums[end] < midvalue){
      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亿浮点数放在内存中，否则就要将数据存储到硬盘中。