数组/List/Map/TreeSet排序总结

冷不防 2024-03-30 15:59 43阅读 0赞

**[Comparator的四种实现][Comparator]**

--------------------

## 数组 ##

**数组升/降序（重排原数组）**

# 基本数据类型
    int[] size = {
        1, 3, 7, 2, 4, 5};
    Arrays.sort(size); // [1, 2, 3, 4, 5, 7]
    
    # 包装类
    Integer[] size1 = {
        1, 3, 7, 2, 4, 5};
    Arrays.sort(size1, Comparator.naturalOrder()); //必须Integer  [1, 2, 3, 4, 5, 7]
    Arrays.sort(size1, Comparator.reverseOrder()); //必须Integer [7, 5, 4, 3, 2, 1]
    
    # 字符
    char[] chars = "bca".toCharArray();
    Arrays.sort(chars); // [a, b, c]
    // Arrays.sort(chars, Comparator.reverseOrder()); // 编译不过
    # Character[] 不存在
    
    # 字符串
    String[] strs = {
        "abc","abe","abd","bc"};
    Arrays.sort(strs); // [abc, abd, abe, bc]
    Arrays.sort(strs, Comparator.reverseOrder()); // [bc, abe, abd, abc]

**数组自定义排序（重排原数组）**

# 二维数组存储书本的长和宽,先长度降序,再宽度降序
    int[][] books = {
        {
        1, 2}, {
        4, 5}, {
        3, 7}, {
        3, 4}};
    
    Arrays.sort(books, (book1, book2) -> {
        
        if (book1[0] == book2[0]) {
         // 长度相等,按宽降序
            return book2[1] - book1[1];
        } else {
        
            return book2[0] - book1[0]; // 优先按照长度降序
        }
    });
    
    排序后：
    [4, 5]
    [3, 7]
    [3, 4]
    [1, 2]

--------------------

## List ##

**List 排序的三种方法**

list.sort(Comparator<? super E> c) 
    list.stream().sorted(Comparator<? super T> comparator);
    
    # 元素本身实现Comparator<? super T>接口 并且Override compareTo方法
    Collections.sort(List<T> list);
    # 元素未实现Comparator<? super T>接口
    Collections.sort(studentList, Comparator<? super E> c))

# 举例
    List<Integer> list223 = Arrays.asList(1, 3, 7, 2, 4, 5);
    
    # 升序（重排原集合）
    list223.sort(Comparator.naturalOrder()); // [1, 2, 3, 4, 5, 7]
    # 降序（重排原集合）
    list223.sort(Comparator.reverseOrder()); // [7, 5, 4, 3, 2, 1]

# 位置颠倒（重排原集合）
    List<Integer> list223 = Arrays.asList(1, 3, 7, 2, 4, 5);
    Collections.reverse(list223);  //[5, 4, 2, 7, 3, 1]
    
    <dependency>
        <groupId>commons-collections</groupId>
        <artifactId>commons-collections</artifactId>
        <version>3.2.1</version>
        <scope>compile</scope>
    </dependency>

--------------------

## Map ##

**注意： (必须用LinkedHashMap::new收集结果)**

Map<Integer, Integer> map = new HashMap<>();
    map.put(1, 11);
    map.put(3, 33);
    map.put(2, 22);
    map.put(5, 55);
    map.put(4, 44);
    
    HashMap<Integer, Integer> res = map.entrySet().stream()
    ----------------------------------------------------------------
    # 按照Key升序
    .sorted((e1, e2) -> e1.getKey() - e2.getKey())
    .sorted((e1, e2) -> e1.getKey().compareTo(e2.getKey()))
    .sorted(Map.Entry.comparingByKey())
    
    # 按照Key降序
    .sorted((e1, e2) -> e2.getKey() - e1.getKey())
    .sorted((e1, e2) -> e2.getKey().compareTo(e1.getKey()))
    .sorted((Map.Entry.<Integer, Integer>comparingByKey().reversed()))
    
    # 按照Value升序
    .sorted((e1, e2) -> e1.getValue() - e2.getValue())
    .sorted((e1, e2) -> e1.getValue().compareTo(e2.getValue()))
    .sorted(Map.Entry.comparingByValue())
    
    # 按照Value降序
    .sorted((e1, e2) -> e2.getValue() - e1.getValue())
    .sorted((e1, e2) -> e2.getValue().compareTo(e1.getValue()))
    .sorted((Map.Entry.<Integer, Integer>comparingByValue().reversed()))
    
    ----------------------------------------------------------------
    # 收集数据(必须用LinkedHashMap::new收集结果)
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e2, LinkedHashMap::new));
    
    {
        5=55, 4=44, 3=33, 2=22, 1=11}

**参考：[Java8 对Map进行排序][Java8 _Map]**

--------------------

## TreeSet ##

# 1、TreeSet本身有序,添加元素即可,但是要求元素实现Comparable<T>重写compareTo方法
    TreeSet<Student> ts = new TreeSet<>();
    
    # 2、创建TreeSet时候把比较器实例传进去
    TreeSet<Student> ts = new TreeSet<Student>(new CustomComparator());
    
    TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
        
        @Override
        public int compare(Student o1, Student o2) {
        
            return (o1.getScore() - o2.getScore());
        }
    });
    
    TreeSet<Student> ts = new TreeSet<>((o1, o2) -> (o1.getScore() - o2.getScore()));

--------------------

## 巧妙排序思路 ##

**[leetcode1839][]. 所有元音按顺序排布的最长子字符串**

----------------------------------------------------------------------
    元音字母的顺序都必须按照 字典序 升序排布
    （也就是说所有的 'a' 都在 'e' 前面，所有的 'e' 都在 'i' 前面，以此类推）
    ----------------------------------------------------------------------
    
    /**
     * leetcode1839. 所有元音按顺序排布的最长子字符串
     * 参考的题解→适合自己的题解
     */
    public static int longestBeautifulSubstring(String word) {
        
        Map<Character, Integer> valueMap = new HashMap();
        valueMap.put('a', 0);
        valueMap.put('e', 1);
        valueMap.put('i', 2);
        valueMap.put('o', 3);
        valueMap.put('u', 4);
        
        char[] chars = word.toCharArray();
        int res = 0;
        
        int start = 0;
        for (int i = 1; i < word.length(); i++) {
        
            // 'a'开始'u'结束且已保证递增，故可以保证（'a' ，'e' ，'i' ，'o' ，'u'）都必须 至少 出现一次
            // 按照 字典序 升序排布
            if (chars[start] == 'a' && (valueMap.get(chars[i - 1]) + 1 == valueMap.get(chars[i]) || valueMap.get(chars[i - 1]) == valueMap.get(chars[i]))) {
        
                if (chars[i] == 'u') {
        
                    res = Math.max(i - start + 1, res);
                }
            } else {
        
                start = i;
            }
        }
        
        return res;
    }

--------------------

[Comparator]: https://blog.csdn.net/weixin_37646636/article/details/132699044
[Java8 _Map]: https://blog.csdn.net/u011663149/article/details/88558758
[leetcode1839]: https://leetcode.cn/problems/longest-substring-of-all-vowels-in-order/