1 堆排序

1.1 算法流程

1. 从n/2-1处开始构建大根堆（使用堆调整算法）

2. 堆顶元素此时为最大值，放入数组末尾，然后重新调整堆

   调整堆算法：

   输入：数组arr、堆长度n、根节点位置root

   1. 初始化左右子树与最大值索引变量，左子树为根节点位置*2，右子树为根节点位置*2+1，最大值索引为根节点索引
   2. 最大值索引变量取左右子树的最大值
   3. 如果此时最大值索引已经不是根节点索引
      • 交换根节点的值与最大索引值
      • 递归调整子树

1.2 代码

public class HeapSort {
    // 主要的堆排序方法
    public static void heapSort(int arr[]) {
        int n = arr.length;
        // 构建最大堆（初始时将数组看作一个完全二叉树）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 一个一个从堆顶取出元素，将最大值放到数组末尾，然后重新调整堆
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶（最大值）和当前未排序部分的最后一个元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 调整堆，排除刚刚交换的元素
            heapify(arr, i, 0);
        }
    }
    // 将子树以root为根的堆调整为最大堆
    public static void heapify(int arr[], int n, int root) {
        int largest = root; // 初始化根节点为最大值
        int leftChild = 2 * root + 1; // 左子节点
        int rightChild = 2 * root + 2; // 右子节点
        // 如果左子节点比根节点大
        if (leftChild < n && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        // 如果右子节点比根节点或左子节点大
        if (rightChild < n && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }
        // 如果最大值不是根节点
        if (largest != root) {
            // 交换根节点和最大值
            int temp = arr[root];
            arr[root] = arr[largest];
            arr[largest] = temp;
            // 递归调整受影响的子树
            heapify(arr, n, largest);
        }
    }
}

2 对哈希表的排序

List<Map.Entry<String, Integer>> sortedEntries = new ArrayList<>(map.entrySet());
        Collections.sort(sortedEntries, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> entry1,
                               Map.Entry<String, Integer> entry2) {
                // 按照value降序排序
                int valueCompare = entry2.getValue().compareTo(entry1.getValue());
                if (valueCompare != 0) {
                    return valueCompare;
                } else {
                    // 如果value相同，按照key升序排序
                    return entry1.getKey().compareTo(entry2.getKey());
                }
            }
        });