Java实现TopK问题的方法

import java.util.Arrays;/** * 使用快排实现的TopK问题 Title: Description: Company: *  * @author 郑伟 * @date 2018年4月10日下午9:28:15 */public class TopK_PartitionSort {  public static void main(String[] args) {    int[] num = { 2, 20, 3, 7, 9, 1, 17, 18, 0, 4 };    partitionSort(num, 0, num.length - 1, 3);    System.out.println(Arrays.toString(num));  }  public static void partitionSort(int[] nums, int low, int high, int K) {    if (low < high) {      int pointKey = partitionSortCore(nums, low, high);      if (K - 1 == pointKey)//TopK问题的核心，就是如果返回的下标为K-1，说明已经排序好了K个最大/最小的数，但是之间的顺序是不确定的        return;      partitionSort(nums, low, pointKey - 1, K);      partitionSort(nums, pointKey + 1, high, K);    }  }  /**   * 快排的核心   *    * @param nums   * @param low   * @param high   * @return 返回排序好以后的位置   */  public static int partitionSortCore(int[] nums, int low, int high) {    // 以第一个座位标志位来比对    int pivotkey = nums[low];    while (low < high) {      // 从pivotkey往最后一个位置比较      while (low < high && pivotkey <= nums[high]) {        --high;      }      // 开始交换pivotkey和nums[high]      int temp = nums[low];      nums[low] = nums[high];      nums[high] = temp;      // 此时nums[high]对应于pivotkey      while (low < high && pivotkey >= nums[low]) {        ++low;      }      // 找到比pivotkey大的书了，那就交换      temp = nums[low];      nums[low] = nums[high];      nums[high] = temp;      // 这时，pivotkey对应于nums[low]    }    return low;// 返回pivotkey对应的正确位置  }}

/** * 使用堆排序实现的TopK问题 Title: Description: Company: *  * @author 郑伟 * @date 2018年4月11日上午9:28:15 */public class TopK_HeapSort {  public static void main(String[] args) {    int[] num = { 2, 20, 3, 7, 9, 1, 17, 18, 0, 4 };    heapSort(num,3);    System.out.println(Arrays.toString(num));  }  /**   * 堆排序   *    * @param num   */  private static void heapSort(int[] num, int K) {    for (int i = num.length / 2 - 1; i >= 0; i--) {      adjustMin(num, i, num.length);// 调整0~num.length-1的数据    }    // 如果要实现topK，就在这里执行    for (int j = num.length - 1; j >= 0 && K > 0; j--,K--) {      // 交换最后一个      swap(num, 0, j);      // 再次调整0~j-1的数据      adjustMin(num, 0, j);    }    //使用最大堆，K=3，输出[9, 7, 3, 2, 4, 1, 0, 17, 18, 20]，最大的三个值17,18,20    //使用最小堆，K=3，输出[3, 4, 9, 7, 20, 18, 17, 2, 1, 0]，最小的三个值2,1,0  }  /**   * 交换栈顶和最后一个元素   *    * @param num   * @param i   * @param j   */  private static void swap(int[] num, int i, int j) {    int tem = num[i];    num[i] = num[j];    num[j] = tem;  }  /**   * 调整为大顶堆   *    * @param num   * @param root_index   */  private static void adjust(int[] num, int root_index, int length) {    //    int root = num[root_index];    for (int j = root_index * 2 + 1; j < length; j = j * 2 + 1) {      // 最大的儿子      if (j + 1 < length && num[j] < num[j + 1]) {        j = j + 1;// 指向了最大的儿子      }      if (root < num[j]) {        num[root_index] = num[j];        root_index = j;// 标记换了哪一个位置      } else {        break;// 已经是大顶堆了，不需要调整了      }    }    num[root_index] = root;  }  /**   * 小顶堆   *    * @param num   * @param root_index   * @param length   */  private static void adjustMin(int[] num, int root_index, int length) {    //    int rootValue = num[root_index];    for (int k = root_index * 2 + 1; k < length; k = k * 2 + 1) {      if (k + 1 < length && num[k] > num[k + 1])        k = k + 1;// K指向最小的子节点      if (num[k] < rootValue) {        num[root_index] = num[k];        root_index = k;// 和k换了一下位置      } else {        break;// 本身不需要再调整了      }    }    num[root_index] = rootValue;  }}