利用堆排序(heapify)和快排(partition)找到top-k个数 java实现

给出一个整数数组m，找到n个最大的数，其中m>=n.

方法一：借助堆排序思想

优点：借助一个n的大小的数组空间，不需要一次性将m全部加载到内存

缺点：每个进入堆的数据都需要经过调整

package com.jimmy.lib;

import java.util.Arrays;

public class MyClass {

    public static void main(String[] args) {
        int m[] = {3, 55, 2, 7, 8, 5, 43, 98, 1, 66, 35, 46, 234, 65};
        int n[] = new int[5];
        System.arraycopy(m, 0, n, 0, n.length);

        // 1. 建立堆
        // 由于是要找到最大的数,我们则需要建立一个最小堆
        for (int i = n.length / 2 - 1; i >= 0; i--) {
            heapify(n, i);
        }

        for (int i = n.length; i < m.length; i++) {
        	// 每次只要比较最小堆顶部的数值
        	if (n[0] < v) {
            	// 如果比顶部的数值大，则替换顶部数值，然后重新调整堆
            	n[0] = v;
            	heapify(n, 0);
            	System.out.println("adjust " + v + " -> " + Arrays.toString(n));
        	}
        }

        System.out.println(Arrays.toString(n));
    }

	/**
 	* 堆调整
 	*/
    private static void heapify(int n[], int i) {
        // 2. 记住左子树和右子树的计算方式
        int left = 2 * i + 1;
        int right = left + 1;
        int root = n[i];

        // 3. 判断左子树是否存在，判断右子树是否存在，比较两者大小，和根的大小比较
        // 4. 如果左边和右边都是正常的，那就直接break循环即可
        while (left < n.length) {
            if (right < n.length && n[right] < n[left] && n[right] < root) {
                n[i] = n[right];
                i = right;
            } else if (n[left] < root) {
                n[i] = n[left];
                i = left;
            } else {
                break;
            }
            n[i] = root;
            left = 2 * i + 1;
            right = left + 1;
        }

    }
}

           

• 输出结果

adjust 5 -> [3, 7, 5, 55, 8]
adjust 43 -> [5, 7, 43, 55, 8]
adjust 98 -> [7, 8, 43, 55, 98]
adjust 66 -> [8, 55, 43, 66, 98]
adjust 35 -> [35, 55, 43, 66, 98]
adjust 46 -> [43, 55, 46, 66, 98]
adjust 234 -> [46, 55, 234, 66, 98]
adjust 65 -> [55, 65, 234, 66, 98]

[55, 65, 234, 66, 98]

           

• 主要思路

1. 先将m的数值填充到n
2. 把n建立成最小堆
3. 遍历m剩下的数值，放入最小堆n中
4. 每次进行调整即可

这个不是完整的堆排序，只是借助了堆排序的思想和方法。

方法二：借助快排思想

优点：比堆排序的速度更快，只需要对部分的数据进行交互即可

缺点：需要将所有的数据都一次性加载到内存，有时也要对所有的数据进行排序

package com.jimmy.lib;

import java.util.Arrays;

public class TopKQuick {

    public static void main(String[] args) {
        int m[] = {3, 55, 2, 7, 8, 5, 43, 98, 1, 66, 35, 46, 234, 65};
        int n = 3;

        quickSortForTopK(m, n, 0, m.length - 1);

        System.out.println(Arrays.toString(m));
    }

    private static void quickSortForTopK(int[] m, int n, int low, int high) {
        int pivot;
        if (low < high) {
            pivot = partition(m, low, high);
            if (n == pivot || n - 1 == pivot) {
                System.out.println(pivot);
                return;
            }
            quickSortForTopK(m, n, low, pivot - 1);
            quickSortForTopK(m, n, pivot + 1, high);
        }
    }
    
	/**
	 * 从大到小的partition
	 */
    private static int partition(int[] m, int low, int high) {
        int pivotKey = m[low];
        while (low < high) {
            while (low < high && pivotKey >= m[high])
                high--;
            m[low] = m[high];
            
            while (low < high && pivotKey <= m[low])
                low++;
            m[high] = m[low];
        }
        m[low] = pivotKey;
        return low;
    }
}

           

• 输出结果

3
[66, 98, 234, 65, 8, 5, 43, 7, 46, 55, 35, 3, 2, 1]
           

• 主要思路

1. 完整的从大到小的快排
2. 增加判断

   pivot

   和

   n

   是否相等的目的是为了减少排序次数

因为当n或者n-1为pivot的时候，那么就意味着前面的n或n-1个数已经是最大的了，接下来不需要在进行排序了