2021-06-07 11:00 已编辑北京林业大学 Java

关注

排序算法总结

备注：

时间复杂度O(n^2)

冒泡排序

public class 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]) {
                    swap(arr, j, j + 1);
                    isSwap = true;
                }
            }
            if (!isSwap) {
                break;
            }
        }
    }

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

LC283 移动零

题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

public class Solution {

    public void moveZeroes(int[] nums) {
        int index = 0;
        // 1.非0元素往前放,index记录放的位置
        for (int num : nums) {
            if (num != 0) {
                nums[index++] = num;
            }
        }
        // 2.[index,n-1]放回0
        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

剑指45 拼接最小数字

题目:输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

public class Solution {

    public String minNumber(int[] nums) {
         // 用list存储String
        List<String> list = new ArrayList<>();
        for (int num : nums) {
            // 将nums中的值转换为String存储进list
            list.add(String.valueOf(num));
        }
        // 拼接数组内所有元素使结果最小，本质上是排序
        // 若字符串拼接 a + b > b + a，那么排序上 b < a;
        list.sort((a, b) -> (a + b).compareTo(b + a));
        // 用res接受结果字符串
        StringBuilder res = new StringBuilder();
        for (String str : list) {
            res.append(str);
        }
        return res.toString();
    }
}

选择排序

public class SelectionSort {

    private static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            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;
    }
}

LC215 找出第K个最大元素

题目：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

public class Solution {

     // 选择排序法:找出K次最大值,返回即可
    public int findKthLargest(int[] nums, int k) {
        // 外层循环k次
        for (int i = 0; i < k; i++) {
            // 找最大值就行
            int maxIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                maxIndex = nums[maxIndex] < nums[j] ? j : maxIndex;
            }
            swap(nums, i, maxIndex);
        }
        // 第一次最大值下标=1-1=0;
        // 第K次最大值下标=k-1
        return nums[k - 1];
    }

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

插入排序

public class InsertionSort {

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j - 1 >= 0 && temp < arr[j - 1]; j--) {
                // 前面的数比temp都大,每个数都依次往后移
                arr[j] = arr[j - 1];
            }
            // 空出的位置放temp
            arr[j] = temp;
        }
    }
}

LC147 对链表进行排序

题目:对链表进行插入排序

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

分析：[1,2,2,3,2]=>[1,2,2,2,3]

初始化：哑结点，last结点指向head，cur结点指向head.next
cur进行遍历，联想[1,2,2,3,2]=>[1,2,2,2,3]交换的过程

public class Solution {

    // 问题：链表的插入排序
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        // 哑结点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null) {
            // 依然有序,pre后移
            if (pre.val <= cur.val) {
                pre = pre.next;
            } else {
                // 倒序,初始化一个lastPre指向哑结点,从头找<=cur.val的最后一个结点的前一个结点
                ListNode lastPre = dummyNode;
                while (lastPre.next.val <= cur.val) {
                    lastPre = lastPre.next;
                }
                // 交换lastPre,pre,cur
                pre.next = cur.next;
                cur.next = lastPre.next;
                lastPre.next = cur;
            }
            // cur移动到pre后面
            cur = pre.next;
        }
        return dummyNode.next;
    }
}

时间复杂度O(nlogn)

希尔排序

希尔排序是对插入排序的一种改进尝试，每次基于一定间隔的的两数进行排序，直到间隔为1再进行插入排序。

在合适步长下，为什么希尔排序可以将时间复杂度降到O(nlogn)？

希尔排序是按照间隔来插入排序，比直接插入排序相邻两个比较消除的逆序多会更多

public class ShellSort {

     // 希尔排序
     public static void shellSort(int[] arr) {
        // 步长step
        int step = arr.length / 2;
        // 插入排序最低就是步长为1
        while (step >= 1) {
            // 以step为距离进行插入排序
            for (int i = step; i < arr.length; i += step) {
                int temp = arr[i];
                int j;
                for (j = i; j - step >= 0 && temp < arr[j - step]; j -= step) {
                    arr[j] = arr[j - step];
                }
                arr[j] = temp;
            }
            step /= 2;
        }
    }


    // 插入排序:最后一步步长是1,不是0
    public static void insertSort(int[] arr) {
        for (int i = 1; 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;
        }
    }
}

LC506 相对名次

题目：给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（"Gold Medal", "Silver Medal", "Bronze Medal"）。

(注：分数越高的选手，排名越靠前。)

示例：

输入: [5, 4, 3, 2, 1]
输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal").
余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。

public class Solution {
     // 排序法+二分查找排名
    public String[] findRelativeRanks(int[] score) {
        int n = score.length;
        int[] copy = new int[n];
        System.arraycopy(score, 0, copy, 0, n);
        Arrays.sort(copy);
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            // 排名+当前排序数组中索引 = 数组长度
            int rank = n - Arrays.binarySearch(copy, score[i]);
            switch (rank) {
                case 1:
                    res[i] = ("Gold Medal");
                    break;
                case 2:
                    res[i] = ("Silver Medal");
                    break;
                case 3:
                    res[i] = ("Bronze Medal");
                    break;
                default:
                    // 不是奖牌排名,就放入排名
                    res[i] = String.valueOf(rank);
            }
        }
        return res;
    }
}

堆排序

堆排序、快速排序、归并排序是面试中最高频的3个面试

public class HeapSort {

  public static void heapSort(int[] arr) {
        if (arr.length < 2) {
            return;
        }
        // 从小到大排序,是建立大根堆
        // 从大到小排序,是建立小根堆
        // 1.自底向上将原数组转换成最大堆，arr[0]是整个数组最大值
        buildMaxHeap(arr);
        // 2.依次交换数组首位（最大值）和数组末尾，然后对剩下的[0,n-1...)再进行堆化操作
        for (int j = arr.length - 1; j >= 0; j--) {
            // 交换大根堆顶部和数组末尾，数据末尾元素来到最终位置
            swap(arr, 0, j);
            // 依次对父节点为0位置,数组长度为i的元素进行堆化操作
            heapify(arr, 0, j);
        }
    }

    // 建立大根堆
    private static void buildMaxHeap(int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    }

    // 对 arr[0, n) 所形成的最大堆中，索引为parent的父节点元素，进行heapify操作
    private static void heapify(int[] arr, int parent, int n) {
        while (2 * parent + 1 < n) {
            int left = 2 * parent + 1;
            if (left + 1 < n && arr[left] < arr[left + 1]) {
                left++;
            }
            // 大根堆,父最大,就停止遍历
            if (arr[left] <= arr[parent]) {
                break;
            }
            // 否则就最大值交换到父节点
            swap(arr, parent, left);
            // 父节点循环进行下去
            parent = left;
        }
    }

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

LC912 排序数组

排序算法是否掌握，可以用力扣912验证

class Solution {

    // 排序算法是否掌握，用力扣912检验
    public int[] sortArray(int[] arr) {
         if (arr.length < 2) {
            return arr;
        }
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        for (int j = arr.length - 1; j >= 0; j--) {
            swap(arr, 0, j);
            heapify(arr, 0, j);
        }
        return arr;
    }

    private static void heapify(int[] arr, int parent, int n) {
        while (2 * parent + 1 < n) {
            int left = 2 * parent + 1;
            if (left + 1 < n && arr[left] < arr[left + 1]) {
                left++;
            }
            // 大根堆,父最大,就停止遍历
            if (arr[left] <= arr[parent]) {
                break;
            }
            swap(arr, parent, left);
            parent = left;
        }
    }

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

LC215 找出第K个最大元素

题目：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

备注：高频面试题，解法很多，但面试官最希望的就是手写堆排序

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

public class Solution {

    // 方法1:手写大根堆
    public int findKthLargest1(int[] nums, int k) {
        buildMaxHeap(nums);
        // 数组首位交换k次,数组首位就是第K大的数
        for (int i = nums.length - 1; i > nums.length - k; i--) {
            swap(nums, 0, i);
            heapify(nums, 0, i);
        }
        return nums[0];
    }


    // 建立大根堆
    private static void buildMaxHeap(int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    }

    // 对 arr[0, n) 所形成的最大堆中，索引为parent的父节点元素，进行heapify操作
    private static void heapify(int[] arr, int parent, int n) {
        while (2 * parent + 1 < n) {
            int left = 2 * parent + 1;
            if (left + 1 < n && arr[left] < arr[left + 1]) {
                left++;
            }
            // 大根堆,父最大,就停止遍历
            if (arr[left] <= arr[parent]) {
                break;
            }
            // 否则就最大值交换到父节点
            swap(arr, parent, left);
            // 父节点循环进行下去
            parent = left;
        }
    }

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

    // 方法2:使用PriorityQueue大根堆
    public int findKthLargest2(int[] nums, int k) {
        // 优先级队列默认是小根堆,拉姆达表达式改成大根堆
        Queue<Integer> maxQueue = new PriorityQueue<>((a, b) -> b - a);
        for (int num : nums) {
            maxQueue.add(num);
        }
        // 第1大的数,第2大的数,第K大的数
        // 移0次     移1次    移K-1次
        for (int i = 0; i < k - 1; i++) {
            maxQueue.remove();
        }
        return maxQueue.peek();
    }

    // 方法2:PriorityQueue小根堆
    public int findKthLargest3(int[] nums, int k) {
        // 因为第k大元素是k个元素中最小的,所以用小根堆
        Queue<Integer> minQueue = new PriorityQueue<>();
        // 先将数组前k个数放入小根堆
        for (int i = 0; i < k; i++) {
            minQueue.add(nums[i]);
        }
        // [1,2,3,4]中第2大的数是3,[1,2]的小根堆顶是2,比下一个数3小所以出队
        // 因为排序后的后k个数虽然是这k个数中最小的,但确实非k个数中最大的,所以小根堆堆顶小了就要出队再入当前元素
        for (int i = k; i < nums.length; i++) {
            if (!minQueue.isEmpty() && minQueue.peek() < nums[i]) {
                minQueue.remove();
                minQueue.add(nums[i]);
            }
        }
        // 此时小根堆堆顶,就是第K大的元素
        return minQueue.peek();
    }

    // 法4:选择排序法
    public int findKthLargest4(int[] nums, int k) {
        // 外层循环k次
        for (int i = 0; i < k; i++) {
            // 找最大值就行
            int maxIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                maxIndex = nums[maxIndex] < nums[j] ? j : maxIndex;
            }
            swap(nums, i, maxIndex);
        }
        // 第一次最大值下标=1-1=0;
        // 第K次最大值下标=k-1
        return nums[k - 1];
    }
}

剑指Offer40 最小的第K个数

public class Solution {
    // 最小的第K个数，用大根堆
    public int[] getLeastNumbers(int[] arr, int k) {
        // 优先级队列默认是小根堆,添加参数修改成大根堆
        Queue<Integer> maxQueue = new PriorityQueue<>(11, (o1, o2) -> o2 - o1);
        // 原数组前k个数放入大根堆
        for (int i = 0; i < k; i++) {
            maxQueue.add(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            // 大根堆堆顶比大，就移除
            if (!maxQueue.isEmpty() && maxQueue.peek() > arr[i]) {
                maxQueue.remove();
                maxQueue.add(arr[i]);
            }
        }
        // 依次移出大根堆，返回结果集数组中
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = maxQueue.remove();
        }
        return res;
    }
}

快速排序

单路快排

public class QuickSort {

     public static void quickSort(int[] arr) {
        // random作为参数一致传递下去
        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, 0, arr.length - 1, 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) {
        int randomIndex = l + random.nextInt(r - l + 1);
        swap(arr, l, randomIndex);
        // j初始化为左边界
        int j = l;
        // 从左边界第一个数开始遍历
        for (int i = l + 1; i < arr.length; i++) {
            // j此时要求是指向<区域最后一个数
            if (arr[i] < arr[l]) {
                // 发现<arr[l],先移动j+1使得j指向>=arr[j]的第一个数,然后交换[i,j]位置的数
                swap(arr, i, j++);
            }
        }
        // 由于循环跳出j指向<区域最后一个数,与基准arr[l]交换
        swap(arr, l, j);
        // 交换后,j指向>=第一个数,返回该数=下标值
        return j;
    }

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

}

双路快排

public class QuickSort {

    // 默写版
    public static void quickSort(int[] arr) {
        // random作为参数一致传递下去
        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) {
        int randomIndex = l + random.nextInt(r - l + 1);
        swap(arr, l, randomIndex);
        // j初始化为左边界
        int j = l;
        // 从左边界第一个数开始遍历
        for (int i = l + 1; i < arr.length; i++) {
            // j此时要求是指向<区域最后一个数
            if (arr[i] < arr[l]) {
                // 发现<arr[l],先移动j+1使得j指向>=arr[j]的第一个数,然后交换[i,j]位置的数
                swap(arr, i, j++);
            }
        }
        // 由于循环跳出j指向<区域最后一个数,与基准arr[l]交换
        swap(arr, l, j);
        // 交换后,j指向>=第一个数,返回该数=下标值
        return j;
    }

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

}

三路快排

public class QuickSort2 {

 public static void quickSort3way(int[] arr) {
        if (arr.length < 2) {
            return;
        }
        Random random = new Random();
        quickSort3way(arr, 0, arr.length - 1, random);
    }

    private static void quickSort3way(int[] arr, int l, int r, Random random) {
        if (l >= r) {
            return;
        }
        // 分治:因为三路快排中间不用递归,避免partition返回值麻烦,所以partition和quickSort3ways写在一起

        int randomIndex = l + random.nextInt(r - l + 1);
        swap(arr, l, randomIndex);
        // 核心：arr[l+1,lt]<v ; arr[lt+1,i-1]=v ; arr[gt,r]>v
        // lt指向<的最后一个元素，i指针遍历，gt指向>的第一个元素
        int lt = l, i = l + 1, gt = r + 1;
        while (i < gt) {
            if (arr[i] < arr[l]) {
                lt++;
                swap(arr, i, lt);
                i++;
            } else if (arr[i] > arr[l]) {
                gt--;
                swap(arr, i, gt);
                // i所在位置从后往前发生了交换,导致nums[i]变新，需要重新比较,i无需++
            } else {
                i++;
            }
        }
        // 交换l位置和小于第一个数
        swap(arr, l, lt);

        // 三路快排抛弃掉中间的部分，不再递归
        quickSort3way(arr, l, lt - 1, random);
        quickSort3way(arr, gt, r, random);

    }


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

}

LC169 最多的数字

题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

public class Solution {
    // 这道题可以用排序法，但是都没有摩尔投票法快
    public int majorityElement(int[] nums) {
        int cur = 0, count = 0;
        for (int num : nums) {
            // count为0,说明要更新遍历数字
            if (count == 0) {
                cur = num;
            }
            // 相同的数组就+1
            if (cur == num) {
                count++;
            } else {
                count--;
            }
        }
        return cur;
    }
}

归并排序

public class MergeSort {

    public static void mergeSort(int[] arr) {
        // 临时数组一开始就创建,传递到merge将arr复制给temp数组
        int[] temp = Arrays.copyOf(arr, arr.length);
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int l, int r, int[] temp) {
        if (l >= r) {
            return;
        }
        // 先递归,划分区域
        int mid = l + (r - l) / 2;
        mergeSort(arr, l, mid, temp);
        mergeSort(arr, mid + 1, r, temp);
        // 再归并,mid>前一个数才归并
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, l, mid, r, temp);
        }
    }

    private static void merge(int[] arr, int l, int mid, int r, int[] temp) {
        System.arraycopy(arr, l, temp, l, r - l + 1);
        int p = l, q = mid + 1;
        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] <= temp[q]) {
                arr[i] = temp[p++];
            } else {
                arr[i] = temp[q++];
            }
        }
    }

}

LC88 合并两个有序数组

题目:给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

public class Solution {
    // 面试最高频的一道题

    // 方法1:双指针,从前往后遍历两个数组,需要辅助数组
    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        // temp存储每次排序好的数组
        int[] temp = new int[m + n];
        // p遍历nums1,q遍历nums2,i遍历temp
        int p = 0, q = 0, i = 0;
        while (p < m && q < n) {
            temp[i++] = nums1[p] < nums2[q] ? nums1[p++] : nums2[q++];
        }
        while (p < m) {
            temp[i++] = nums1[p++];
        }
        while (q < n) {
            temp[i++] = nums2[q++];
        }
        // 将temp数组遍历回nums1
        System.arraycopy(temp, 0, nums1, 0, m + n);
    }

    // 方法2:双指针,从后往前遍历两个数组,放最大,不需要辅助数组
    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        int p = m - 1, q = n - 1, i = m + n - 1;
        // 从后往前找大的放入nums1中
        while (p >= 0 && q >= 0) {
            nums1[i--] = nums1[p] < nums2[q] ? nums2[q--] : nums1[p--];
        }
        // p<0上面遍历结束,此时q还没遍历到0,将nums2从[0,q+1)复制到nums1中
        System.arraycopy(nums2, 0, nums1, 0, q + 1);
    }
}

LC21 合并两个有序链表

题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

递归的解法，常看动图，加深理解：力扣21递归解法查看

public class Solution {

    // 迭代法:preHead.next返回结果，pre用于调整较小值
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        // 设定一个哑结点,方便返回值
        ListNode dummyNode = new ListNode(-1);
        // cur指针指向每次比较的较小值结点
        ListNode cur = dummyNode;
        while (l1 != null && l2 != null) {
            // 判断较小值,cur指向它
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            // 判断完后移cur
            cur = cur.next;
        }
        // 循环结束,cur指向非空链表头部
        cur.next = (l1 == null) ? l2 : l1;
        return dummyNode.next;
    }

    // 递归法：判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果
    // 因为l1、l2有序,所以递归最后一定是指向一个最短有序链表的,然后递归依次返回
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        // 递归结束条件:谁遍历到最后为null,返回另一个
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        // 递归判断，每一次都返回最小值结点进递归栈
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }
    }
}

剑指51 数组中的逆序对问题

题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

public class Solution {

   // 将res作为参数传递,会出现各种问题,直接定义成员变量省事
    private int res;

    // 归并排序法，原理是利用nums[i]>nums[j],那么[i,mid]中都是逆序对个数
    public int reversePairs(int[] nums) {
        int[] temp = new int[nums.length];
        res = 0;
        mergeSort(nums, 0, nums.length - 1, temp);
        return res;
    }

    private void mergeSort(int[] nums, int l, int r, int[] temp) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        mergeSort(nums, l, mid, temp);
        mergeSort(nums, mid + 1, r, temp);
        if (nums[mid] > nums[mid + 1]) {
            merge(nums, l, mid, r, temp);
        }
    }

    private void merge(int[] nums, int l, int mid, int r, int[] temp) {
        System.arraycopy(nums, l, temp, l, r - l + 1);
        int p = l, q = mid + 1;
        for (int i = l; i <= r; i++) {
            if (p > mid) {
                nums[i] = temp[q++];
            } else if (q > r) {
                nums[i] = temp[p++];
            } else if (temp[p] <= temp[q]) {
                // <=区域不会形成逆序对,所以和归并排序过程一样
                nums[i] = temp[p++];
            } else {
                // >说明必构成逆序对:[p,mid]与[mid+1,...]构成逆序对mid-p+1
                res += mid - p + 1;
                nums[i] = temp[q++];
            }
        }
    }
}

非比较算法O(n)

计数排序

计数排序不基于元素的比较，只基于元素的出现次数，用R来表示一个元素的取值范围，利用count[R]记录每个元素出现次数，index[R+1]记录nums排好序后[index[i],index[i+1])的值为i
计数排序是稳定的,这是它最关键的一个性质

力扣75 颜色分类

题目:给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：

输入：nums = [0]
输出：[0]

示例 4：

输入：nums = [1]
输出：[1]

public class Solution {

    // 方法1:简单的记录出现元素次数，但对于理解计数排序法非常有帮助
    public void sortColors1(int[] nums) {
        // count数组记录0,1,2在nums中出现的次数
        int[] count = new int[3];
        for (int num : nums) {
            if (num == 0) {
                count[0]++;
            } else if (num == 1) {
                count[1]++;
            } else {
                count[2]++;
            }
            // 以上的写法可以等价:count[num]++;
        }
        // 注意下标之间的连接
        for (int i = 0; i < count[0]; i++) {
            nums[i] = 0;
        }
        for (int i = count[0]; i < count[1] + count[0]; i++) {
            nums[i] = 1;
        }
        for (int i = count[1] + count[0]; i < count[2] + count[1] + count[0]; i++) {
            nums[i] = 2;
        }
    }

    // 方法2:计数排序法,这个方法有点像桶排序
    public void sortColors2(int[] nums) {
        // 1.定义元素取值范围:[0,3)
        int R = 3;
        int[] cnt = new int[R];
        // 记录出现的次数
        for (int num : nums) {
            cnt[num]++;
        }
        // 2.index表示:nums排好序后[index[i],index[i+1])的值为i
        // 因为0之前没有元素，单独用0位置存，所以是R+1个长度
        int[] index = new int[R + 1];
        // 只遍历到n-1的位置,因为末尾元素无cnt[R+1]对应
        for (int i = 0; i < index.length - 1; i++) {
            index[i + 1] = index[i] + cnt[i];
        }
        // 3.再次遍历到n-1,nums[index[i],index[i+1])=i
        for (int i = 0; i < index.length - 1; i++) {
            for (int j = index[i]; j < index[i + 1]; j++) {
                nums[j] = i;
            }
        }
    }
}

力扣1122 数组的相对顺序

题目：给你两个数组，arr1和 arr2，

arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

提示：数组长度不大于1k,每个元素取值返回不大于1k，就是提示你用计数排序法

1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中

public class Solution {

    // 计数排序法,取值范围为[0,1000]所以可以考虑使用计数排序法
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // 1.找到arr1中最大值max,生成count[max+1]，count[0,max]记录arr1每个元素出现次数
        int max = 0;
        for (int num : arr1) {
            max = Math.max(num, max);
        }
        // 2.只用计数排序中的count数组记录次数就行,不需要index数组
        int[] count = new int[max + 1];
        for (int num : arr1) {
            count[num]++;
        }
        int[] res = new int[arr1.length];
        int index = 0;
        // 3.遍历arr2中元素,回count[num]=出现次数,放回res中
        for (int num : arr2) {
            for (int i = 0; i < count[num]; i++) {
                res[index++] = num;
            }
            // 重点:用过的count[num]清零,说明
            count[num] = 0;
        }
        // 4.遍历count,非0元素遍历个数回res中
        for (int i = 0; i < count.length; i++) {
            if (count[i] != 0) {
                for (int j = 0; j < count[i]; j++) {
                    res[index++] = i;
                }
            }
        }
        return res;
    }
}

基数排序

什么是数字的高位和低位？比如102，高位是1，低位是2，不要弄反

LSD算法

适用于等长字符串，通常不会用于数字的比较
如果用于比较数字，可以将数字转换为字符串数组，不等长的数字，前面高位补0再转换，并不会改变原排序位置
但是LSD不能用于非等长字符串，字符串补空格是行不通的，\0也是不行（某些语言\0是字符串结尾标识）
如果要比较非等长字符串，那就要用MSD算法

public class LSDSort {

    // 参数提供一个len,提示调用者arr中元素等长的长度
    public static void lSDSort(String[] arr, int len) {
        // LSD算法,多用于字符串排序,这里参数直接使用字符串数组;并且LSD只适用于等长字符串
        // LSD:Least significant digital,比如"ABC"中的“C”是低位,“A”是高位
        for (String s : arr) {
            if (s.length() != len) {
                throw new IllegalArgumentException("All Strings' length must be the same.");
            }
        }
        // Java中Char占1个字节=256位,取值范围0-255
        int R = 256;
        int[] cnt = new int[R];
        int[] index = new int[R + 1];
        // 辅助数组
        String[] temp = new String[arr.length];
        // LSD:从每个字符的末尾开始使用计数排序
        for (int i = len - 1; i >= 0; i--) {
            // 每次遍历开始,记录次数前清空cnt
            Arrays.fill(cnt, 0);
            // 记录次数
            for (String s : arr) {
                cnt[s.charAt(i)]++;
            }
            // 记录index数组
            for (int j = 0; j < index.length - 1; j++) {
                index[j + 1] = index[j] + cnt[j];
            }
            // 根据index,将各字符放回temp数组
            for (String s : arr) {
                // index[s.charAt(i)]=是s起始出现的坐标
                temp[index[s.charAt(i)]] = s;
                // 下一次出现的坐标+1
                index[s.charAt(i)]++;
            }
            // 遍历temp赋值给原数组arr
            for (int j = 0; j < arr.length; j++) {
                arr[j] = temp[j];
            }
        }

    }

    public static void main(String[] args) {
        String[] arr = {"a", "c", "d"};
        LSDSort.lSDSort(arr, 1);
        System.out.println(Arrays.toString(arr));
    }

}

MSD算法

边界处理：空（长度不够）对应的“字符值”最小,比如空比“A”还小
- 假设原先字符取值范围[0,R-1]R种可能，现在加上空值的可能，字符取值范围为[1,R]+[0]，规定[0]是空，长度为R+1

public class MSDSort {

    public static void mSDSort(String[] arr) {
        int N = arr.length;
        String[] temp = new String[N];
        mSDSort(arr, 0, N - 1, 0, temp);
    }

    /**
     * @param arr   待排序数组arr
     * @param left  对arr[i]待排序的最左边字符串
     * @param right 对arr[i]待排序的最右边字符串
     * @param r     arr[i]的r位置,处理arr[left, right]
     * @param temp  辅助数组一次性开辟出来
     */
    private static void mSDSort(String[] arr, int left, int right, int r, String[] temp) {
        // 递归结束条件
        if (left >= right) {
            return;
        }
        // 开始修改计数排序

        // 字符取值范围
        int R = 256;
        // 由于有null值,index和cnt数组比LSD都要加一位
        // 规定cnt[0]记录空值出现的次数
        int[] cnt = new int[R + 1];
        int[] index = new int[R + 2];

        // 记录arr[i]中r位置字符出现的次数
        for (int i = left; i <= right; i++) {
            // 越界:r位置如果超过了字符的长度=遇到了空值,规定了cnt[0]记录空值,所以cnt[0]++
            // 正常:cnt[arr[i].charAt(r) + 1]++
            cnt[r >= arr[i].length() ? 0 : (arr[i].charAt(r) + 1)]++;
        }
        // 记录次数
        for (int i = 0; i < cnt.length; i++) {
            index[i + 1] = index[i] + cnt[i];
        }
        // 赋值给temp数组
        for (int i = left; i <= right; i++) {
            int p = r >= arr[i].length() ? 0 : (arr[i].charAt(r) + 1);
            temp[left + index[p]] = arr[i];
            index[p]++;
        }
        // temp赋值回原数组
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }

        // 计数排序修改完成,开始递归,需要深刻理解
        for (int i = 0; i < R; i++) {
            mSDSort(arr, left + index[i], left + index[i + 1] - 1, r + 1, temp);
        }
    }

}

桶排序

public class BucketSort {

    // 桶排序1:桶记录每个元素出现的次数
    public static void bucketSort1(Integer[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 1.从所有数中找出最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        // 2.生成max+1个元素的桶,使得桶[0,max]
        int[] bucket = new int[max + 1];
        // 3.遍历数组，每个元素出现的个数加入桶
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        // 4.遍历桶，将非0数据放回原数组
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }

    /**
     * 桶排序2:用户指定每个桶的长度,另一种思维
     *
     * @param arr 待排序数组
     * @param c   每个桶的长度
     */
    public static void bucketSort2(int[] arr, int c) {
        if (c <= 0) {
            throw new IllegalArgumentException("c must be >0");
        }
        // 计算桶的数量
        int B = arr.length / c + (arr.length % c > 0 ? 1 : 0);
        List<Integer>[] buckets = new List[B];
        for (int i = 0; i < B; i++) {
            buckets[i] = new LinkedList<>();
        }
        // 找出数组中的最小值
        int min = Integer.MAX_VALUE;
        for (int num : arr) {
            min = Math.min(min, num);
        }
        // 元素如桶：在几号桶? = (arr[i]-min)/桶数c
        for (int num : arr) {
            buckets[(num - min) / c].add(num);
        }
        // 使用库函数对每个桶中元素进行排序
        for (int i = 0; i < buckets.length; i++) {
            Collections.sort(buckets[i]);
        }
        // 将桶中元素，放回原数组
        int index = 0;
        for (int i = 0; i < buckets.length; i++) {
            for (Integer num : buckets[i]) {
                arr[index++] = num;
            }
        }
    }
}

力扣164 最大间距

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

public class Solution {

    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        // 1.统计数组长度,最大值,最小值
        int N = nums.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        // 如果最大值和最小值相同,最大间距为0,直接返回
        if (min == max) {
            return 0;
        }
        // 2.生成3个桶,每个桶长N+1
        boolean[] hasNum = new boolean[N + 1];
        int[] maxs = new int[N + 1];
        int[] mins = new int[N + 1];
        // 3.最大值桶只放区间最大值，最小值桶只放区间最小值
        // bid是桶id,记录放入桶的编号
        int bid = 0;
        // 有几个数就要遍历几次=遍历N次
        for (int i = 0; i < N; i++) {
            // 算出每个元素放入桶中的id
            bid = getBucketId(nums[i], N, min, max);
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
            hasNum[bid] = true;
        }
        // 4.排序后，相邻元素的最大差值=(当前非空桶最小值-上一个非空桶最大值)中的最大值
        int maxGap = 0;
        int lastMax = maxs[0];
        // 从第2个桶开始统计最大差值
        for (int i = 1; i <= N; i++) {
            if (hasNum[i]) {
                // 相邻元素的最大差值=(当前非空桶最小值-上一个非空桶最大值)中的最大值
                maxGap = Math.max(maxGap, mins[i] - lastMax);
                // 更新上一个非空桶的最大值
                lastMax = maxs[i];
            }
        }
        return maxGap;
    }

    // 计算num放入哪个桶:(arr[i]-min)/桶长,桶长=(max-min)/len
    // 注意:数据类型全部用long,因为有乘法int会溢出
    private int getBucketId(long num, long len, long min, long max) {
        return (int) ((num - min) * len / (max - min));
    }
}

LC561 数组拆分I

题目：给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该最大总和。

示例 1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：

1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
   所以最大总和为 4

示例 2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

public class Solution {
    // 力扣561:2n长度数组拆分n对(a,b)形式，找出每队最小值之和的最大和
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        // 排序后,间隔为2的每位数之和=n对最小值之和的最大和
        for (int i = 0; i < nums.length; i += 2) {
            res += nums[i];
        }
        return res;
    }
}

排序算法总结

情绪（稳定性）不稳定：快（快速排序）些（希尔排序）选（选择排序）堆（堆排序）

排序名称	时间复杂度	空间复杂度	稳定性	备注
冒泡排序	O(n^2)，完全有序变成O(n)	O(1)	稳定	力扣283移动数字0
选择排序	O(n^2)	O(1)	不稳定	运行时间和输入无关；数据移动是最少的
插入排序	O(n^2)，完全有序变成O(n)	O(1)	稳定	排序时间取决于初始值（使用交换方式）
希尔排序	O(nlogn)-O(n^2)	O(1)	不稳定	分组思想
堆排序	O(nlogn)	O(1)	不稳定	实现优先队列
快速排序	O(nlogn)，含有相同元素数组，三路快排O(n)	O(1)	不稳定	求解topK等问题
归并排序	O(nlogn)，完全有序变成O(n)	O(n)	稳定	求解逆序对、小和、染色等问题