数据结构必备代码

目录：

• 排序算法
• 树的遍历
• 查找
• 链表插入
• 数组与列表转化
• 二维数组排序
• java中输入
• 集合遍历

一、基本排序
1、冒泡排序
思路：从左到右不断交换相邻逆序的元素，一轮交换之后，可以让未排序的元素上浮到右侧（每次确定一个该次遍历最大的值）；

package com.bj.sort;
/**
* 1、冒泡排序
*
*/
public class Test1 {
    public static void sort(int [] nums){
         int len = nums.length;
         // 遍历的轮次
         for (int i = 0; i < len-1; i++) {
             boolean isSorted = false; // 是否有序的标记
             // 相邻元素比较，每次冒出一个最大的数据
             for (int j = 0; j < len-1-i; j++) {
                 if(nums[j]>nums[j+1]){
                      isSorted = true;
                      swap(nums,j,j+1);
                 }
             }
             if(!isSorted) return;
         }
    }
    // 交换元素
    private static void swap(int[] nums, int j, int  i) {
         int temp = nums[j];
         nums[j] = nums[i];
         nums[i] = temp;
    }
    public static void main(String[] args) {
         int nums [] = {6,3,8,2,9,1};
         sort(nums);
         for(int item:nums){
             System.out.print(item+" ");
         }
    }
}

2、选择排序
思路：选择出数组中的最小元素，将它与数组中第一个元素交换，从剩下的元素中选择最小的元素，将它与第二个元素交换位置，依次循环；（每次确定一个该次遍历的最小值）；

package com.bj.sort;
/**
* 2、选择排序
*
*/
public class Test2 {
    public static void sort(int [] nums){
         int len = nums.length;
         int minIndex = 0; // 最小值的下标
         for (int i = 0; i < len-1; i++) {
             minIndex = i;
             for (int j = i+1; j < len; j++) {
                 if(nums[minIndex]>nums[j])  minIndex = j;
             }
             swap(nums,minIndex,i); // 交换最小值和当前元素(每次选出一个最小值放在前面)
         }
    }
    // 交换元素
    private static void swap(int[] nums, int j, int  i) {
         int temp = nums[j];
         nums[j] = nums[i];
         nums[i] = temp;
    }
    public static void main(String[] args) {
         int nums [] = {6,3,8,2,9,1};
         sort(nums);
         for(int item:nums){
             System.out.print(item+" ");
         }
    }
}

3、插入排序
思路：从左到右进行，每次都将当前元素插入到左侧已经排序的数组中，使得插入后左部数据依然有序；

package com.bj.sort;
/**
* 3、插入排序
*
*/
public class Test3 {
    public static void sort(int [] nums){
         int len = nums.length;
         for (int i = 0; i < len-1; i++) {
             for (int j = i+1; j > 0; j--) {
                 if(nums[j]<nums[j-1])  swap(nums,j,j-1);
                 else break;
             }
         }
    }
    // 交换元素
    private static void swap(int[] nums, int j, int  i) {
         int temp = nums[j];
         nums[j] = nums[i];
         nums[i] = temp;
    }
    public static void main(String[] args) {
         int nums [] = {6,3,8,2,9,1};
         sort(nums);
         for(int item:nums){
             System.out.print(item+" ");
         }
    }
}

4、希尔排序（缩小增量排序）
思路：将待排序序列拆分为多个子序列，保证每个子序列内部有序，然后不断减小区间大小，最终保证区间长度为1都有序；

package com.bj.sort;
/**
* 4、希尔排序
*
*/
public class Test4 {
    public static void sort(int [] nums){
         int len = nums.length;
         for (int i = len/2; i > 0; i = i/2) {
             // 内部为插入排序
             for (int j = 0; j < len-i; j = j+i) {
                 for (int k = j+i; k > 0; k = k-i)  {
                      if(nums[k] < nums[k-i])  swap(nums, k, k-i);
                      else break;
                 }
             }
         }
    }
    // 交换元素
    private static void swap(int[] nums, int j, int  i) {
         int temp = nums[j];
         nums[j] = nums[i];
         nums[i] = temp;
    }
    public static void main(String[] args) {
         int nums [] = {6,3,8,2,9,1};
         sort(nums);
         for(int item:nums){
             System.out.print(item+" ");
         }
    }
}

5、归并排序
思路：将数组不断划分，保证其有序，然后对有序数组进行合并；

package com.bj.sort;
/**
* 5、归并排序
*
*/
public class Test5 {
    public static void sort(int [] nums, int low,  int high){
         if(low<high){
             int mid = (low+high)/2;
             sort(nums, low, mid); // 划分
             sort(nums, mid+1, high);
             merge(nums, low, mid, high); // 归并
         }
    }
    // 合并区间
    private static void merge(int[] nums, int low,  int mid, int high) {
         int len = nums.length;
         int i = low, m = mid, j = mid+1, n = high;
         int index = 0;
         int [] temp = new int[len];
         while(i<=m && j<=n){
             if(nums[i] < nums[j]) temp[index++] =  nums[i++];
             else temp[index++] = nums[j++];
         }
         while(i<=m) temp[index++] = nums[i++];
         while(j<=n) temp[index++] = nums[j++];
         // 应用归并的结果修改原数组数据
         for (int k = 0; k < index; k++) {
             nums[k+low] = temp[k];
         }
    }
    public static void main(String[] args) {
         int nums [] = {6,3,8,2,9,1};
         sort(nums,0,nums.length-1);
         for(int item:nums){
             System.out.print(item+" ");
         }
    }
}

6、快速排序
思路：在数组中选择一个基准点，然后分别从数组的两端扫描数组，设两个指示标志，然后从后半部分开始，如果发现有元素比该基准点的值小，交换二者的值，然后从前半部分开始扫描，发现有元素大于基准点的值就交换，如此循环，直到二者达到同一位置，把基准点的值放在该位置，一次排序完成；

package com.bj.sort;
/**
* 6、快速排序
*
*/
public class Test6 {
    public static void sort(int [] nums, int low,  int high){
         if(low>=high) return;
         int index = findBase(nums,low,high);
         sort(nums, low, index-1);
         sort(nums, index+1, high);
    }
    // 针对基准数据排序
    private static int findBase(int[] nums, int low,  int high) {
         int baseData = nums[low];
         while(low < high){
             while(low < high && nums[high] >=  baseData) high--;
             nums[low] = nums[high];
             while(low < high && nums[low] <=  baseData) low++;
             nums[high] = nums[low];
         }
         nums[low] = baseData;
         return low;
    }
    public static void main(String[] args) {
         int nums [] = {6,3,8,2,9,1};
         sort(nums,0,nums.length-1);
         for(int item:nums){
             System.out.print(item+" ");
         }
    }
}

7、堆排序
思路：将待排序的序列构成一个大顶堆，此时整个序列最大值为堆顶根节点，将它与末尾交换，然后将剩余的一个序列重新构成一个堆，这样得到的n个元素中次大的值，如此反复，便能得到一个有序序列；

package com.bj.sort;
/**
* 7、堆排序
*
*/
public class Test7 {
    public static void sort(int [] nums){
         int len = nums.length;
         for (int i = len/2-1; i >= 0; i--) {
             adjustHeap(nums,i,len); // 初始化堆
         }
         for (int i = len-1; i >= 0; i--) {
             swap(nums,0,i); // 与第一个元素交换
             adjustHeap(nums,0,i); // 调整堆
         }
    }
    private static void adjustHeap(int[] nums, int  i, int len) {
         int temp = nums[i]; // 定义当前根节点
         for (int j = 2*i+1; j < len; j = j*2) { //  递归左孩子
             if(j+1 < len && nums[j] < nums[j+1])  j++;
             if(temp > nums[j]) break; // 已经为局部最大堆，退出
             nums[i] = nums[j]; // 将最大叶子节点赋值给根节点
             i = j; // 当前节点为根节点
         }
         nums[i] = temp;
    }
    private static void swap(int[] nums, int j, int  i) {
         int temp = nums[j];
         nums[j] = nums[i];
         nums[i] = temp;
    }
    
    public static void main(String[] args) {
         int nums [] = {6,3,8,2,9,1};
         sort(nums);
         for(int item:nums){
             System.out.print(item+" ");
         }
    }
}

8、计数排序
思路：将所有数据映射到桶中，统计其出现次数，然后依次取出；（不同的值占不同的桶）；

package com.bj.sort;
/**
* 8、计数排序
*
*/
public class Test8 {
    public static void sort(int [] nums){
         int len = nums.length;
         int max = maxData(nums); // 求最大值
         int [] count = new int[max+1]; // 声明桶数组
         // 遍历数组，统计个数
         for (int i = 0; i < len; i++)  count[nums[i]]++;
         int index = 0;
         // 将数据复制
         for (int i = 0; i <= max; i++) {
             // 一个值出现多次
             while(count[i]-- > 0) nums[index++] =  i;
         }
    }
    // 求最大值
    private static int maxData(int[] nums) {
         int max = Integer.MIN_VALUE;
         for (int i = 0; i < nums.length; i++) {
             if(nums[i] > max) max = nums[i];
         }
         return max;
    }
    public static void main(String[] args) {
         int nums [] = {6,3,8,2,9,1};
         sort(nums);
         for(int item:nums){
             System.out.print(item+" ");
         }
    }
}

9、桶排序
思路：将数值映射到桶中，桶内使用其他排序算法排序，依次按桶输出；

package com.bj.sort;
import java.util.ArrayList;
import java.util.Collections;
/**
* 9、桶排序
*
*/
public class Test9 {
    public static void sort(int [] nums){
        int len = nums.length;
        int max = maxData(nums);
        int min = minData(nums);
        // 定义桶，并初始化
        int bucketNum = (max-min)/len+1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<ArrayList<Integer>>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }
        // 将元素放入桶内
        for (int i = 0; i < len; i++) {
            int num = (nums[i]-min)/len;
            bucketArr.get(num).add(nums[i]);
        }
        // 对桶内元素排序
        for (int i = 0; i < bucketNum; i++) {
            Collections.sort(bucketArr.get(i));
        }
        // 元素复制
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            for (int j = 0; j < bucketArr.get(i).size(); j++) {
                nums[index++] = bucketArr.get(i).get(j);
            }
        }
    }
    // 求最小值
    private static int minData(int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] < min) min = nums[i];
        }
        return min;
    }
    // 求最大值
    private static int maxData(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > max) max = nums[i];
        }
        return max;
    }
    public static void main(String[] args) {
        int nums [] = {6,3,8,2,9,1};
        sort(nums);
        for(int item:nums){
            System.out.print(item+" ");
        }
    }
}

10、基数排序
思路：按照低位先排序，再按照高位排序，依次类推，直到最高位；

package com.bj.sort;
import java.util.ArrayList;
/**
* 10、基数排序
*
*/
public class Test10 {
    public static void sort(int [] nums){
         int len = nums.length;
         int max = maxData(nums); // 求最大值
         // 数字的位数
         int maxDigit = 1;
         while(max/10!=0){
             maxDigit++;
         }
         // 定义桶，并初始化
         ArrayList<ArrayList<Integer>> bucketArr =  new ArrayList<ArrayList<Integer>>();
         for (int i = 0; i < 10; i++) {
             bucketArr.add(new  ArrayList<Integer>());
         }
         int div = 1; // 数字的权重
         for (int i = 0; i < maxDigit; i++,div =  div*10) {
             // 根据数据当前位的数决定放在哪一个桶中
             for (int j = 0; j < len; j++) {
                 int num = (nums[j]/div)%10;
                 bucketArr.get(num).add(nums[j]);
             }
             // 取出桶中元素
             int index = 0;
             for (int j = 0; j < bucketArr.size();  j++) {
                 for (int k = 0; k <  bucketArr.get(j).size(); k++) {
                      nums[index++] =  bucketArr.get(j).get(k);
                 }
                 bucketArr.get(j).clear(); // 清空桶内元素
             }
         }
    }
    private static int maxData(int[] nums) {
         int max = Integer.MIN_VALUE;
         for (int i = 0; i < nums.length; i++) {
             if(nums[i] > max) max = nums[i];
         }
         return max;
    }
    public static void main(String[] args) {
         int nums [] = {6,3,8,2,9,1};
         sort(nums);
         for(int item:nums){
             System.out.print(item+" ");
         }
    }
}

排序算法性能分析

二、树的递归
0、创建树

package com.bj.tree.traverse;
import java.util.ArrayList;
import java.util.List;
/**
* 0、创建树
*
*/
public class TreeNode {
    private int data; // 节点值
    private TreeNode left; // 左节点
    private TreeNode right; // 右节点
    private TreeNode root; // 根节点
    
    public TreeNode() {
    }
    public TreeNode(int data) {
        this.data = data;
    }
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public TreeNode getLeft() {
        return left;
    }
    public void setLeft(TreeNode left) {
        this.left = left;
    }
    public TreeNode getRight() {
        return right;
    }
    public void setRight(TreeNode right) {
        this.right = right;
    }
    public TreeNode getRoot() {
        return root;
    }
    public void setRoot(TreeNode root) {
        this.root = root;
    }
    // 构建树
    public void create(int[] data2){
        List<TreeNode> list = new ArrayList<TreeNode>();
        for(int temp:data2) list.add(new TreeNode(temp));
        root = list.get(0);
        for (int i = 0; i < list.size()/2; i++) {
            if(i*2+1 < list.size())
                list.get(i).setLeft(list.get(i*2+1));
            if(i*2+2<list.size())
                list.get(i).setRight(list.get(i*2+2));
        }    
    }
}

1、先序遍历

package com.bj.tree.traverse;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 1、先序遍历
*
*/
public class Test1 {
    private static List<Integer> list = new ArrayList<Integer>();
    // 递归实现
    public static List<Integer> preOrderTraversal(TreeNode root){
        if(root!=null){
            list.add((Integer) root.getData());
            preOrderTraversal(root.getLeft());
            preOrderTraversal(root.getRight());
        }
        return list;
    }
    // 栈实现
    public static List<Integer> preOrderTraversal1(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node==null) continue;
            list.add(node.getData());
            stack.add(node.getRight());
            stack.add(node.getLeft());
        }
        return list;
    }
    public static void main(String[] args) {
        int data [] = {1,2,3,4,5};
        TreeNode binTree = new TreeNode();
        binTree.create(data);
        List<Integer> list = preOrderTraversal1(binTree.getRoot());
        for(int item:list){
            System.out.print(item+" ");
        }
    }
}

2、中序遍历

package com.bj.tree.traverse;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 2、中序遍历
*
*/
public class Test2 {
    private static List<Integer> list = new ArrayList<Integer>();
    // 递归实现
    public static List<Integer> preOrderTraversal(TreeNode root){
        if(root!=null){
            preOrderTraversal(root.getLeft());
            list.add((Integer) root.getData());
            preOrderTraversal(root.getRight());
        }
        return list;
    }
    // 栈实现
    public static List<Integer> preOrderTraversal1(TreeNode root){
        if(root==null) return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while(cur!=null || !stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur = cur.getLeft();
            }
            TreeNode node = stack.pop();
            list.add(node.getData());
            cur = node.getRight();
        }
        return list;
    }
    public static void main(String[] args) {
        int data [] = {1,2,3,4,5};
        TreeNode binTree = new TreeNode();
        binTree.create(data);
        List<Integer> list = preOrderTraversal(binTree.getRoot());
        for(int item:list){
            System.out.print(item+" ");
        }
    }
}

3、后序遍历

package com.bj.tree.traverse;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
/**
* 3、后序遍历
*
*/
public class Test3 {
    private static List<Integer> list = new ArrayList<Integer>();
    // 递归实现
    public static List<Integer> preOrderTraversal(TreeNode root){
        if(root!=null){
            preOrderTraversal(root.getLeft());
            preOrderTraversal(root.getRight());
            list.add(root.getData());
        }
        return list;
    }
    // 栈实现
    public static List<Integer> preOrderTraversal1(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node==null) continue;
            list.add(node.getData());
            stack.add(node.getLeft());
            stack.add(node.getRight());
        }
        Collections.reverse(list);
        return list;
    }
    public static void main(String[] args) {
        int data [] = {1,2,3,4,5};
        TreeNode binTree = new TreeNode();
        binTree.create(data);
        List<Integer> list = preOrderTraversal1(binTree.getRoot());
        for(int item:list){
            System.out.print(item+" ");
        }
    }
}

4、层次遍历

package com.bj.tree.traverse;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 4、层次遍历
*
*/
public class Test4 {
    private static List<Integer> list = new ArrayList<Integer>();
    // 队列实现
    public static List<Integer> layerTraversal(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            int cnt = queue.size();
            while(cnt-->0){
                TreeNode node = queue.poll();
                if(node==null) continue;
                list.add(node.getData());
                queue.add(node.getLeft());
                queue.add(node.getRight());
            }
        }
        return list;
    }
    public static void main(String[] args) {
        int data [] = {1,2,3,4,5};
        TreeNode binTree = new TreeNode();
        binTree.create(data);
        List<Integer> list = layerTraversal(binTree.getRoot());
        for(int item:list){
            System.out.print(item+" ");
        }
    }
}

三、查找（二分查找）

package com.bj.search;
import javax.swing.plaf.synth.SynthSeparatorUI;
/**
* 二分查找
* @author 流浪
*
*/
public class Test1 {
    public static int binarySearch(int [] nums, int  target){
         int low = 0, high = nums.length-1;
         while(low<=high){
             int mid = (low+high)/2;
             if(nums[mid]==target) return mid;
             else if (nums[mid]>target) high =  mid-1;
             else low = mid+1;
         }
         return -1;
    }
    public static void main(String[] args) {
         int [] nums = {1,2,3,4,5};
         int target = 2;
         System.out.println(binarySearch(nums,  target));
    }
}

四、链表
1、头插法

package com.bj.linkedlist;
import java.util.List;
/**
* 头插法
* @author 流浪
*
*/
public class Test2 {
    public static class ListNode{
         int val;
         ListNode next = null;
         public ListNode(int val){
             this.val = val;
         }
    }
    public ListNode addToLinkHead(List<Integer>  list){
         ListNode node = new ListNode(-1);
         node.next = null;
         for (int i = 0; i < list.size(); i++) {
             ListNode temp = new  ListNode(list.get(i));
             temp.next = node.next;
             node.next = temp;
         }
         return node.next;
    }
    public ListNode addToLinkHead(ListNode head){
         ListNode node = new ListNode(-1);
         while(head!=null){
             ListNode temp = head.next; // 保存节点信息
             head.next = node.next; // 将当前节点连接断开
             node.next = head; // 连接节点
             head = temp; // 节点后移
         }
         return node.next;
    }
}

2、尾插法

package com.bj.linkedlist;
import java.util.List;
/**
* 尾插法
*
*/
public class Test1 {
    public static class ListNode{
         int val;
         ListNode next = null;
         public ListNode(int val){
             this.val = val;
         }
    }
    public ListNode addToLinkHead(List<Integer>  list){
         ListNode node = new ListNode(-1);
         ListNode root = node;
         for (int i = 0; i < list.size(); i++) {
             ListNode temp = new  ListNode(list.get(i));
             node.next = temp;
             node = temp;
         }
         return root.next;
    }
}

五、数组与列表转化
数组与列表转化

package com.bj.arrayAndList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Test1 {
    public static void main(String[] args) {
         // 列表转数组
         List<Integer> list = new  ArrayList<Integer>(Arrays.asList(1, 2, 3,4));
         Integer [] num = list.toArray(new  Integer[0]);
         for(int item:num){
             System.out.print(item+" ");
         }
         System.out.println();
         // 数组转列表
         Integer [] nums = {1,2,3,4};
         List<Integer> list1 = Arrays.asList(nums);
         for(int item:list1){
             System.out.print(item+" ");
         }
    }
}

六、二维数组排序

package com.bj.array.sort;
import java.util.Arrays;
import java.util.Comparator;
public class Test1 {
    public static void main(String[] args) {
         int [][] nums = {{1,5},{2,6},{3,4}};
         Arrays.sort(nums, new Comparator<int [] >()  {
             @Override
             public int compare(int[] o1, int[] o2)  {
                 // 其中o2-o1表示降序，其中o2[0]表示根据第一维度排序
                 return o2[0]-o1[0];
             }
         });
         for (int i = 0; i < nums.length; i++) {
             for (int j = 0; j < nums[i].length;  j++) {
                 System.out.print(nums[i][j]+" ");
             }
             System.out.println();
         }
    }
}

七、java中输入
1、输入切换
说明：java中nextInt()后接nextLine()读取不到，因为在缓存区中遇到“空格”，“回车符”等空白字符串时会将空白字符前的数据读取走，但空白字符不会被处理掉；

package com.bj.input;
import java.util.Scanner;
/**
* 输入切换
*
*/
public class Test1 {
    public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         while(scan.hasNext()){
             int m = scan.nextInt();
             scan.nextLine();
             String str = scan.nextLine();
             System.out.println(m+","+str);
         }
         scan.close();
    }
}

2、不定长输入

package com.bj.input;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* 不定长输入
*
*/
public class Test2 {
    public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         List<Integer> list = new  ArrayList<Integer>();
         while(true){
             String str = scan.nextLine();
             if(str==null || str.trim().length()==0)  break;
             String strs[] = str.split(" ");
             for (int i = 0; i < strs.length; i++) {
                 list.add(Integer.parseInt(strs[i]));
             }
         }
         for(int item:list){
             System.out.print(item+" ");
         }
         scan.close();
    }
}

八、集合遍历
1、HashMap遍历

package com.bj.collection;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;
/**
* HashMap遍历
*
*/
public class Test2 {
    public static void main(String[] args) {
         HashMap<Integer,String> map = new  HashMap<Integer,String>();
         map.put(1, "a");
         map.put(2, "b");
         map.put(3, "c");
         // key遍历
         Set<Integer> set = map.keySet();
         for(int item:set){
             System.out.print(item+" ");
         }
         System.out.println();
         // key,value遍历
         Set<Entry<Integer, String>> entry =  map.entrySet();
         for(Entry<Integer,String> item:entry){
             System.out.print(item.getKey()+":"+item.getValue()+"  ");
         }
         System.out.println();
         // 只获取value
         Collection<String> values = map.values();
         for(String item:values){
             System.out.print(item+" ");
         }
    }
}

2、Set遍历

package com.bj.collection;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/**
* HashSet遍历
*
*/
public class Test1 {
    public static void main(String[] args) {
         Set<String> set = new  HashSet<String>(Arrays.asList("a","b"));
         // 迭代器方式
         Iterator<String> iter = set.iterator();
         while(iter.hasNext()){
             System.out.print(iter.next()+" ");
         }
         System.out.println();
         // for循环
         for(String item:set){
             System.out.print(item+" ");
         }
    }
}

3、HashMap排序

package com.bj.collection;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
/**
* HashMap排序
*
*/
public class Test3 {
    public static void main(String[] args) {
         HashMap<Integer,String> map = new  HashMap<Integer,String>();
         map.put(1, "a");
         map.put(2, "b");
         map.put(3, "c");
         List<Map.Entry<Integer,String>> list = new  ArrayList<Map.Entry<Integer,String>>(map.entrySet());
         Collections.sort(list,new  Comparator<Map.Entry<Integer,String>>() {
             @Override
             public int compare(Entry<Integer,  String> o1, Entry<Integer, String> o2) {
                 return  o2.getValue().compareTo(o1.getValue()); // 根据值降序
             }
         });
         // key,value遍历
         for(Map.Entry<Integer,String> item:list){
             System.out.print(item.getKey()+":"+item.getValue()+"  ");
         }
    }
}