排序算法总结

情绪（稳定性）不稳固：快些选堆

抉择排序

public class SelectionSort {private SelectionSort() { }

    // 默写版
    public static void selectionSort(int[] arr) {for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {minIndex = arr[minIndex] < arr[j] ? minIndex : j;
            }
            swap(arr, i, minIndex);
        }
    }

    private static void swap(int[] arr, int i, int j) {int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 抉择排序 1: 从前到后选最小
    public static <E extends Comparable<E>> void selectionSort(E[] arr) {for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                // 循环不变量：minIndex 永远指向最小的元素
                minIndex = arr[minIndex].compareTo(arr[j]) < 0 ? minIndex : j;
            }
            swap(arr, i, minIndex);
        }
    }

    // 抉择排序 2 从后到前选最大
    public static <E extends Comparable<E>> void selectionSort1(E[] arr) {for (int i = arr.length - 1; i >= 0; i--) {
            int maxIndex = i;
            for (int j = i - 1; j >= 0; j--) {maxIndex = arr[j].compareTo(arr[maxIndex]) > 0 ? j : maxIndex;
            }
            swap(arr, i, maxIndex);
        }
    }


    private static <E> void swap(E[] arr, int i, int j) {E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

插入排序

public class InsertionSort {private InsertionSort() { }


    // 默写版
    private static void insertSort(int[] arr) {for (int i = 0; i < arr.length; i++) {int temp = arr[i];
            int j;
            // 从后往前插
            for (j = i; j - 1 >= 0 && temp < arr[j - 1]; j--) {arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

    // 插入排序 1: 取出元素插入，前面希尔排序会用到这种形式
    public static <E extends Comparable<E>> void insertSort1(E[] data) {
        // 外层循环：遍历每个数组元素，i 右边曾经排好序，左边待排序
        for (int i = 0; i < data.length; i++) {
            // 取出以后遍历第一个元素，将它插入到后面曾经排好序的数组中，适合的地位
            E temp = data[i];
            // 内层循环：遍历右边曾经排好序的数组
            int j;
            // && 左边的条件不能下放！因为 j -- 会对一个位移
            for (j = i; j - 1 >= 0 && temp.compareTo(data[j - 1]) < 0; j--) {data[j] = data[j - 1];
            }
            // 内层产生挪动，空出的 j 地位赋值给 temp
            // 内层没有产生挪动，temp 原地赋值给本人
            data[j] = temp;
        }
    }


    // 插入排序 2: 应用替换，性能没有下面好
    public static <E extends Comparable<E>> void insertSort2(E[] arr) {for (int i = 1; i < arr.length; i++) {for (int j = i - 1; j >= 0 && arr[j].compareTo(arr[j + 1]) > 0; j++) {swap(arr, j, j + 1);
            }
        }
    }

    private static <E> void swap(E[] arr, int j, int i) {E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

}

练习题

LC147_对链表进行排序

public class Solution {public ListNode insertionSortList(ListNode head) {if (head == null) {return null;}
        // 初始化三个指针：dummyNode 避免 cur 插入到 head 地位
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode lastSorted = head;
        ListNode cur = head.next;
        // cur 指针遍历，循环完结条件是 cur==null
        while (cur != null) {
            // lastSorted 后移条件
            if (lastSorted.val <= cur.val) {lastSorted = lastSorted.next;} else {
                // 否则, 从头遍历链表找最初 <=cur.val 的节点
                ListNode pre = dummyNode;
                while (pre.next.val <= cur.val) {pre = pre.next;}
                // 将 cur 插入到 pre 后一位，扭转三者指向
                lastSorted.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
            // cur 为待插入结点 =last 后一位
            cur = lastSorted.next;
        }
        // 返回 dummyNode 下一位
        return dummyNode.next;
    }
}

冒泡排序

public class BubbleSort {private BubbleSort() { }

    // 默写版
    private static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwap = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {swap1(arr, j, j + 1);
                    isSwap = true;
                }
            }
            if (!isSwap) {break;}
        }
    }

    // 不应用额定空间，不思考数字越界的替换
    private static void swap1(int[] arr, int i, int j) {arr[j] = arr[i] + arr[j];
        arr[i] = arr[j] - arr[i];
        arr[j] = arr[j] - arr[i];
    }


    // 冒泡排序惯例写法: 从后往前比拟，这种写法比拟好记
    public static <E extends Comparable<E>> void bubbleSort0(E[] arr) {
        // 只须要 n - 1 层内部循环
        for (int i = arr.length - 1; i > 0; i--) {for (int j = 0; j < i; j++) {if (arr[j].compareTo(arr[j + 1]) > 0) {swap(arr, j, j + 1);
                }
            }
        }
    }

    // 冒泡排序 1: 优化设置替换标记位
    public static <E extends Comparable<E>> void bubbleSort1(E[] arr) {
        // 外层实现比拟次数：n- 1 次
        for (int i = 0; i < arr.length - 1; i++) {
            // 优化：设置替换标记位
            boolean isSwap = false;
            // 内层实现相邻元素比拟：每趟只比拟 j 和 j + 1 的元素
            for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j].compareTo(arr[j + 1]) > 0) {swap(arr, j, j + 1);
                    isSwap = true;
                }
            }
            // 内层没有产生替换，阐明后面曾经都排好序了，就不必再次比拟
            if (!isSwap) {break;}
        }
    }

    // 冒泡排序 2: 优化设置最初替换地位，勾销掉 i ++
    public static <E extends Comparable<E>> void bubbleSort2(E[] arr) {for (int i = 0; i < arr.length - 1;) {
            int swapNextIndex = 0;
            for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j].compareTo(arr[j + 1]) > 0) {swap(arr, j, j + 1);
                    // 最初替换地位必定是靠后的 j +1
                    swapNextIndex = j + 1;
                }
            }
            i = arr.length - swapNextIndex;
        }
    }


    private static <E> void swap(E[] arr, int i, int j) {E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

希尔排序

希尔排序是对插入排序的一种改良尝试，每次基于肯定距离的的两数进行排序，直到距离为 1 再进行插入排序，此时简直有序插入排序效率变高

public class ShellSort {private ShellSort() { }

    /**
     * 希尔排序: 对插入排序一种优化，又叫放大增量排序，每次将数组一个元素与雷同增量区间比拟排序，直到增量为 1
     */


    // 希尔排序 1: 利用插入排序更改
    public static <E extends Comparable<E>> void shellSort1(E[] arr) {
        // 希尔的步长
        int step = arr.length / 2;
        while (step >= 1) {
            // 插入排序
            insertSort(arr, step);
            step = step / 2;
        }
    }

    private static <E extends Comparable<E>> void insertSort(E[] arr, int step) {for (int i = step; i < arr.length; i++) {E t = arr[i];
            int j;
            for (j = i; j - step >= 0 && t.compareTo(arr[j - step]) < 0; j -= step) {arr[j] = arr[j - step];
            }
            arr[j] = t;
        }
    }

    // 希尔排序 2：三重循环
    public static <E extends Comparable<E>> void shellSort2(E[] arr) {
        // 希尔的步长
        int step = arr.length / 2;
        while (step >= 1) {
            // start 是每个子数组的起始地位
            for (int start = 0; start < step; start++) {
                // 以下是应用插入排序
                // 对每个子数组进行插入排序:data[start+step,start+2h...data.length-1]
                for (int i = start + step; i < arr.length; i += step) {E temp = arr[i];
                    int j;
                    // 前一个元素是 j -step
                    for (j = i; j - step >= 0 && temp.compareTo(arr[j - step]) < 0; j -= step) {arr[j] = arr[j - step];
                    }
                    arr[j] = temp;
                }
            }
            step = step / 2;
        }
    }


    // 希尔排序 3：批改步长序列
    public static <E extends Comparable<E>> void shellSort3(E[] arr) {
        // 希尔的步长
        int step = 1;
        while (step < arr.length) {step = step * 3 + 1;}
        while (step >= 1) {// 对每个子数组进行插入排序:data[start+h,start+2h...data.length-1]
            for (int i = step; i < arr.length; i++) {E temp = arr[i];
                int j;
                // 前一个元素是 j -step
                for (j = i; j - step >= 0 && temp.compareTo(arr[j - step]) < 0; j -= step) {arr[j] = arr[j - step];
                }
                arr[j] = temp;
            }
            step = step / 3;
        }
    }
}

练习题

LC506_绝对名次

public class Solution {
    // 排序法
    public String[] findRelativeRanks1(int[] score) {String[] result = new String[score.length];
        // 复制原数组到排序数组
        int[] sorted = new int[score.length];
        System.arraycopy(score, 0, sorted, 0, score.length);
        Arrays.sort(sorted);
        for (int i = 0; i < score.length; i++) {int index = score.length - Arrays.binarySearch(sorted, score[i]);
            switch (index) {
                case 1:
                    result[i] = "Gold Medal";
                    break;
                case 2:
                    result[i] = "Silver Medal";
                    break;
                case 3:
                    result[i] = "Bronze Medal";
                    break;
                default:
                    result[i] = String.valueOf(index);
            }
        }
        return result;
    }

    // 计数排序法
    public String[] findRelativeRanks2(int[] score) {String[] result = new String[score.length];
        int max = Integer.MIN_VALUE;
        for (int num : score) {max = Math.max(max, num);
        }
        int[] array = new int[max + 1];
        // 初始化 arr 数组, 下标为 score 的值，arr[i]为该元素的排名
        for (int i = 0; i < score.length; i++) {array[score[i]] = i + 1;
        }
        int rank = 1;
        for (int i = array.length - 1; i >= 0; i--) {if (array[i] != 0) {switch (rank) {
                    case 1:
                        result[array[i] - 1] = "Gold Medal";
                        break;
                    case 2:
                        result[array[i] - 1] = "Silver Medal";
                        break;
                    case 3:
                        result[array[i] - 1] = "Bronze Medal";
                        break;
                    default:
                        result[array[i] - 1] = String.valueOf(rank);
                }
                rank++;
            }
        }
        return result;
    }
}

归并排序

第一种版本是进行优化后的，便于对了解数组中的逆序对问题！

public class MergeSort {private MergeSort() { }

    public static <E extends Comparable<E>> void mergerSort(E[] arr) {
        // 优化: 只生成一次辅助数组，使得 merge 中没有偏移量的操作了
        // Arrays.copyOf(指标数组, 开区间)
        E[] temp = Arrays.copyOf(arr, arr.length);
        mergerSort(arr, 0, arr.length - 1, temp);
    }

    private static <E extends Comparable<E>> void mergerSort(E[] arr, int l, int r, E[] temp) {
        // 优化 2：指定长度内，可应用间接插入排序优化，但这种优化成果不显著，所以这里放弃应用
        if (l >= r) {return;}
        // 先递归合成
        int mid = l + (r - l) / 2;
        mergerSort(arr, l, mid, temp);
        mergerSort(arr, mid + 1, r, temp);
        // 优化 1：[l,mid]曾经排序好，[mid+1...]后的地位
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {merge(arr, l, mid, r, temp);
        }
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {// System.arraycopy(复制数组, 复制数组起始地位, 指标数组, 指标数组起始地位, 复制数组长度开区间)
        System.arraycopy(arr, l, temp, l, r - l + 1);
        // p 遍历 temp[l,mid];q 遍历 temp[mid+1,r]
        int p = l, q = mid + 1;
        // i 遍历 arr[l,r]
        for (int i = l; i <= r; i++) {if (p > mid) {arr[i] = temp[q++];
            } else if (q > r) {arr[i] = temp[p++];
            } else if (temp[p].compareTo(temp[q]) <= 0) {arr[i] = temp[p++];
            } else {arr[i] = temp[q++];
            }
        }
    }
}

第二版是左程元上课时教的，集体认为是最容易了解和背诵的版本，但不利于书写数组逆序对问题

public class MergeSort1 {private MergeSort1() { }

    // 左神归并排序写法
    public static void mergeSort(int[] arr) {if (arr.length < 2) {return;}
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int l, int r) {if (l == r) {return;}
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l, int m, int r) {int[] temp = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r) {temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {temp[i++] = arr[p1++];
        }
        while (p2 <= r) {temp[i++] = arr[p2++];
        }
        for (i = 0; i < temp.length; i++) {arr[l + i] = temp[i];
        }
    }

    private static void swap(int[] arr, int i, int j) {int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

练习题

LC88_合并两个有序数组

十分高频的一道题

public class Solution {

    /**
     * 合并两个有序数组，num1 长度大于 m +n,m 是 num1 长度，n 是 nums2 长度
     */

    // 办法一: 逆向双指针，不应用额定数组
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 初始化为各自 - 1 的地位
        int p1 = m - 1, p2 = n - 1, tail = m + n - 1;
        // temp 存较大的数，从后往前放
        int temp;
        while (p1 >= 0 || p2 >= 0) {
            // temp 获取较大值
            if (p1 == -1) {temp = nums2[p2--];
            } else if (p2 == -1) {temp = nums1[p1--];
            } else if (nums1[p1] < nums2[p2]) {temp = nums2[p2--];
            } else {temp = nums1[p1--];
            }
            // 利用尾指针寄存 temp
            nums1[tail--] = temp;
        }
    }

    // 办法二: 正向双指针，须要应用额定数组
    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        // 初始化从 0 开始
        int p1 = 0, p2 = 0;
        // 辅助变量存比拟后的值
        int temp;
        int[] help = new int[m + n];
        while (p1 < m || p2 < n) {if (p1 == m) {temp = nums2[p2++];
            } else if (p2 == n) {temp = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {temp = nums1[p1++];
            } else {temp = nums2[p2++];
            }
            // 辅助数组放下 temp
            help[p1 + p2 - 1] = temp;
        }
        // 从 help 数组的 0 地位开始复制 m + n 个元素到 nums1 数组中，nums1 数组从 0 地位开始承受
        System.arraycopy(help, 0, nums1, 0, m + n);
    }
}

剑指 25_合并两个有序链表

public class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // dummyNode 便于返回头结点
        ListNode dummyNode = new ListNode(0);
        // cur 初始化指向 dummyNode
        ListNode cur = dummyNode;
        while (l1 != null && l2 != null) {if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            // 每次循环，cur 后移
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dummyNode.next;
    }
}

剑指 52_数组中的逆序对问题

这道题十分高频，并且对于了解归并排序的归并操作有很大帮忙，倡议 dubug 多看几次

public class Solution {
    private int res;

    // 归并排序法，如果右边大，那么右边未归并的局部就是造成逆序对的个数
    public int reversePairs(int[] nums) {int[] temp = new int[nums.length];
        res = 0;
        sort(nums, 0, nums.length - 1, temp);
        return res;
    }

    private void sort(int[] arr, int l, int r, int[] temp) {if (l >= r) {return;}
        int mid = l + (r - l) / 2;
        sort(arr, l, mid, temp);
        sort(arr, mid + 1, r, temp);
        // > 保障了，如果 j 地位小于 i 地位的，右边未排序中的必定是逆序对
        if (arr[mid] > arr[mid + 1]) {merge(arr, l, mid, r, temp);
        }
    }

    private void merge(int[] arr, int l, int mid, int r, int[] temp) {System.arraycopy(arr, l, temp, l, r - l + 1);
        int i = l, j = mid + 1;
        // 每轮循环为 arr[k] 赋值
        for (int k = l; k <= r; k++) {if (i > mid) {arr[k] = temp[j++];
            } else if (j > r) {arr[k] = temp[i++];
            } else if (temp[i] <= temp[j]) {arr[k] = temp[i++];
            } else {// 判断逆序对条件：temp[i]>temp[j]
                res += mid - i + 1;
                arr[k] = temp[j++];
            }
        }
    }
}

疾速排序

单路快排

public class QuickSort {private QuickSort() { }

    // 单路快排默写版
    public static void quickSort(int[] arr) {if (arr == null || arr.length < 2) {return;}
        Random random = new Random();
        quickSort(arr, 0, arr.length - 1, random);
    }

    private static void quickSort(int[] arr, int l, int r, Random random) {if (l >= r) {return;}
        int p = partition(arr, l, r, random);
        quickSort(arr, l, p - 1, random);
        quickSort(arr, p + 1, r, random);
    }

    private static int partition(int[] arr, int l, int r, Random random) {swap(arr, l, l + random.nextInt(r - l + 1));
        int less = l;
        for (int i = l + 1; i <= r; i++) {if (arr[i] < arr[l]) {swap(arr, i, ++less);
            }
        }
        swap(arr, l, less);
        return less;
    }


    public static <E extends Comparable<E>> void quickSort1(E[] arr) {Random random = new Random();
        quickSort1(arr, 0, arr.length - 1, random);
    }

    private static <E extends Comparable<E>> void quickSort1(E[] arr, int l, int r, Random random) {
        // 不仅仅是递归完结条件, 更是上轮 l 和 r 保障左小右大的条件
        if (l >= r) return;
        // 将数组分区，随机取得一个基数，小于基数放右边，大于基数放左边，返回基数最终地位下标
        int p = partition1(arr, l, r, random);
        // 对上一轮基数最终地位的右边，递归排序
        quickSort1(arr, l, p - 1, random);
        // 对上一轮基数最终地位的左边，递归排序
        quickSort1(arr, p + 1, r, random);
    }

    // partition: 数组分区，随机取得一个基数，小于基数放右边，大于基数放左边，返回基数最终地位下标
    private static <E extends Comparable<E>> int partition1(E[] arr, int l, int r, Random random) {
        // 随机替换 l 和 p 地位上的数，解决数组有序问题
        int p = l + random.nextInt(r - l + 1);
        swap1(arr, l, p);
        // j 初始化 l
        int j = l;
        // 遍历 l 后续数组元素，j 指向 <arr[l]的最初一个数，for (int i = l + 1; i <= r; i++) {if (arr[i].compareTo(arr[l]) < 0) {
                j++;
                swap1(arr, i, j);
            }
        }
        // 循环跳出, 替换基数与小于基数最初一个数
        swap1(arr, l, j);
        // 因为上一步替换，此时 arr[j]就是基数最终地位，返回 j
        return j;
    }


    private static <E> void swap1(E[] arr, int i, int j) {E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    private static void swap(int[] arr, int i, int j) {int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

双路快排

public class QuickSort2Ways {private QuickSort2Ways() { }

    // 双路疾速排序
    public static <E extends Comparable<E>> void quickSort2ways(E[] arr) {Random random = new Random();
        quickSort2ways(arr, 0, arr.length - 1, random);
    }

    private static <E extends Comparable<E>> void quickSort2ways(E[] arr, int l, int r, Random random) {if (l >= r) return;
        int p = partition(arr, l, r, random);
        quickSort2ways(arr, l, p - 1, random);
        quickSort2ways(arr, p + 1, r, random);
    }

    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random random) {int p = l + random.nextInt(r - l + 1);
        swap(arr, l, p);
        // i 指向 <= 的区间的下一个元素，j 指向 >= 区间的前一个元素
        int i = l + 1, j = r;
        while (true) {while (i <= j && arr[i].compareTo(arr[l]) < 0) {i++;}
            while (i <= j && arr[j].compareTo(arr[l]) > 0) {j--;}
            // 循环条件:i<j; 相同就是完结条件
            if (i >= j) {break;}
            // 循环未完结, 此时 arr[i]>= 基数,arr[j]<= 基数，替换使得前小后大
            swap(arr, i, j);
            // 挪动指针
            i++;
            j--;
        }
        // 循环跳出条件 i >=j,arr[j]指向 <=arr[l]的最初一个数, 替换(l,j)
        swap(arr, l, j);
        return j;
    }

    private static <E> void swap(E[] arr, int i, int j) {E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

三路快排

public class QuickSort3Ways {private QuickSort3Ways() { }

    // 三路快排
    public static <E extends Comparable<E>> void quickSort3ways(E[] arr) {Random random = new Random();
        quickSort3ways(arr, 0, arr.length - 1, random);
    }

    private static <E extends Comparable<E>> void quickSort3ways(E[] arr, int l, int r, Random random) {if (l >= r) return;
        int p = l + random.nextInt(r - l + 1);
        swap(arr, l, p);
        // 外围：arr[l+1,lt]<v ; arr[lt+1,i-1]=v ; arr[gt,r]>v
        // less 指向 < 的最初一个元素，i 指针遍历，more 指向 > 的第一个元素
        int less = l, i = l + 1, more = r + 1;
        while (i < more) {if (arr[i].compareTo(arr[l]) < 0) {
                less++;
                swap(arr, i, less);
                i++;
            } else if (arr[i].compareTo(arr[l]) > 0) {
                more--;
                swap(arr, i, more);
                // 原先的 gt-- 后的值没有比拟过，i 持续指向它，不必 i ++
            } else {// arr[i]==arr[l]
                i++;
            }
        }
        swap(arr, l, less);
        // 三路快排摈弃掉两头的局部，不再递归
        quickSort3ways(arr, l, less - 1, random);
        quickSort3ways(arr, more, r, random);
    }


    private static <E> void swap(E[] arr, int i, int j) {E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

练习题

LC69_少数元素

public class Solution {
    // 排序法
    public int majorityElement(int[] nums) {Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    // map 法
    public int majorityElement1(int[] nums) {Map<Integer, Integer> map = countMap(nums);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if (entry.getValue() > (nums.length) / 2) {return entry.getKey();
            }
        }
        throw new RuntimeException("not have num");
    }

    private Map<Integer, Integer> countMap(int[] nums) {Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {if (!map.containsKey(num)) {map.put(num, 1);
            } else {map.put(num, map.get(num) + 1);
            }
        }
        return map;
    }

    // 候选人投票法
    public int majorityElement2(int[] nums) {int res = nums[0], res_count = 1;
        for (int i = 1; i < nums.length; i++) {if (res == nums[i]) {res_count++;} else {
                res_count--;
                if (res_count == 0) {
                    // 候选人投票数为 0, 重置候选人为下一个数
                    res = nums[i];
                    res_count = 1;
                }
            }
        }
        return res;
    }
}

堆排序

public class HeapSort {private HeapSort() { }

    // 基础知识: 设根节点 0 开始为 i，左孩子 2i+1, 右孩子 2i+2
    // 设左右孩子为 i，父亲节点为(i-1)/2

    // 堆排序：原地堆排序
    public static <E extends Comparable<E>> void heapSort(E[] arr) {if (arr.length <= 1) {return;}
        // 1. 对数组最右子树父节点顺次上浮操作，循环完结 arr[0]= 数组 max
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {siftUp(arr, i, arr.length);
        }
        // 2. 第一次 arr[0]=max, 与数组开端替换，每次替换，都对 [0,i) 进行下沉操作使得 arr[0]=max
        for (int i = arr.length - 1; i >= 0; i--) {swap(arr, 0, i);
            siftUp(arr, 0, i);
        }

    }

    // 对 arr[0,bound)所造成的最大堆中, 索引为 parentIndex 的父亲和其左右孩子，进行最大值上浮操作
    private static <E extends Comparable<E>> void siftUp(E[] arr, int parentIndex, int bound) {while (2 * parentIndex + 1 < bound) {
            int left = 2 * parentIndex + 1;
            if (left + 1 < bound && arr[left + 1].compareTo(arr[left]) > 0) {
                // left 指向最大孩子节点下标
                left++;
            }
            // 循环完结条件: 父元素比孩子最大还大
            if (arr[parentIndex].compareTo(arr[left]) >= 0) {break;}
            // 否则: 替换父元数和孩子最大值
            swap(arr, parentIndex, left);
            // 父指针指向孩子最大值下标
            parentIndex = left;
        }
    }


    private static <E> void swap(E[] arr, int i, int j) {E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

练习题

LC23_合并 K 个升序数组

public class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) {return null;}
        // 最小值堆: 依照 lists 中 node 的值从小到大排列。雷同的值依照原先顺序排列
        PriorityQueue<ListNode> minQueue = new PriorityQueue<>(lists.length, (node1, node2) -> {if (node1.val < node2.val) {return -1;} else if (node1.val == node2.val) {return 0;} else {return 1;}
        });
        // 哑结点和遍历指针
        ListNode dummyNode = new ListNode(0);
        ListNode cur = dummyNode;
        // 遍历原 lists，将所有结点放入最小值堆中
        for (ListNode node : lists) {if (node != null) {minQueue.add(node);
            }
        }
        // 遍历最小值堆，每次让 cur 指向出队的元素，cur 后移，再让 cur.next 从新入队，始终让堆顶放弃最小值
        while (!minQueue.isEmpty()) {cur.next = minQueue.poll();
            cur = cur.next;
            if (cur.next != null) {minQueue.add(cur.next);
            }
        }
        return dummyNode.next;
    }
}