排序算法总结

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

抉择排序

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;
    }
}