Java原生排序方法总结--HashMap排序

阳光穿透心脏的1/2处 2022-07-21 01:24 131阅读 0赞

import：java.util.Arrays;

java.util.Comparator

**一、Arrays.sort()对基本类型排序（应该不是最优）**

其中主要分为Primitive(8种基本类型)和Object两大类。

基本类型：采用调优的快速排序；

对象类型：采用改进的归并排序。

![Center][]

**二.Comparator--对象排序**

对于整数、字符串排序，jdk提供了默认的实现，如果要对一个对象数组排序，则要自己实现java.util.Comparator接口。

源码中的内置的快速排序，主要做了以下几个方面的优化：

1）当待排序的数组中的元素个数较少时，源码中的阀值为7，采用的是插入排序。尽管插入排序的时间复杂度为0(n^2)，但是当数组元素较少时，插入排序优于快速排序，因为这时快速排序的递归操作影响性能。

2）较好的选择了划分元（基准元素）。能够将数组分成大致两个相等的部分，避免出现最坏的情况。例如当数组有序的的情况下，选择第一个元素作为划分元，将使得算法的时间复杂度达到O(n^2).

源码中选择划分元的方法:

当数组大小为 size=7 时 ，取数组中间元素作为划分元。int n=m>>1;(此方法值得借鉴)

当数组大小 7<size<=40时，取首、中、末三个元素中间大小的元素作为划分元。

当数组大小 size>40 时 ，从待排数组中较均匀的选择9个元素，选出一个伪中数做为划分元。

3）调整划分元 v

普通的快速排序算法，经过一次划分后，将划分元排到素组较中间的位置，左边的元素小于划分元，右边的元素大于划分元，          Arrays.sort()中得到了较大的优化：将与划分元相等的元素放在其附近。

举例：15、93、15、41、6、15、22、7、15、20

因  7<size<=40,所以在15、6、和20 中选择v = 15 作为划分元。

经过一次换分后： 15、15、7、6、41、20、22、93、15、15. 与划分元相等的元素都移到了素组的两边。

接下来将与划分元相等的元素移到数组中间来，形成：7、6、15、15、15、15、41、20、22、93.

最后递归对两个区间进行排序\[7、6\]和\[41、20、22、93\].

**三.应用实例**

**　　**

**3.1基本排序**

//1. 数字排序 
           int[] intArray = new int[] { 4, 1, 3, -23 };
    　　Arrays.sort(intArray);
    　　//输出： [-23, 1, 3, 4]
    　   //2. 字符串排序，先大写后小写 String[] strArray = new String[] { "z", "a", "C" };
    　　Arrays.sort(strArray);
    　　//输出： [C, a, z]
    　　//3. 严格按字母表顺序排序，也就是忽略大小写排序 Case-insensitive sort
    　　Arrays.sort(strArray, String.CASE_INSENSITIVE_ORDER);
    　　//输出： [a, C, z]
    　　//4. 反向排序， Reverse-order sort
    　　Arrays.sort(strArray, Collections.reverseOrder());
    　　//输出：[z, a, C]
    　　//5. 忽略大小写反向排序 Case-insensitive reverse-order sort
    　　Arrays.sort(strArray, String.CASE_INSENSITIVE_ORDER);
    　　Collections.reverse(Arrays.asList(strArray));
    　　//输出： [z, C, a]

**3.2对象排序**

import java.util.Arrays;  
    import java.util.Comparator;  
      
    class Person {  
        private String name;  
        private float weight;  
          
        public Person(String name, float weight) {  
            setName(name);  
            setWeight(weight);  
        }  
          
        public Person() {  
          
        }  
          
        public String getName() {  
            return name;  
        }  
          
        public float getWeight() {  
            return weight;  
        }  
          
        public void setName(String name) {  
            this.name = name;  
        }  
          
        public void setWeight(float weight) {  
            this.weight = weight;  
        }  
    }  
      
    //创建一个比较器  
    class PersonComparator implements Comparator {  
        public final int compare(Object c1, Object c2) {  
            if(((Person)c1).getWeight() > ((Person)c2).getWeight()) {  
                return 1;  
            } else if(((Person)c1).getWeight() == ((Person)c2).getWeight()) {  
                        return 0;  
            } else return -1;  
        }  
    }  
      
    public class T1 {  
        public static void main(String[] args) {  
            Person c1 = new Person("jack", 100);  
            Person c2 = new Person("paul", 50);  
            Person c3 = new Person("ming", 80);  
            Person[] c = new Person[]{c1, c2, c3};  
              
            System.out.println("排序前:");  
            for( Person c4 : c) {  
                System.out.print(c4.getName() + "," + c4.getWeight() + "\t");  
            }  
      
            Arrays.sort(c, new PersonComparator());  
      
            System.out.println("\n排序后:");  
            for( Person c4 : c) {  
                System.out.print(c4.getName() + "," + c4.getWeight() + "\t");  
            }  
        }  
    }

**结果：**  
排序前:  
jack,100.0 paul,50.0 ming,80.0   
排序后:  
paul,50.0 ming,80.0 jack,100.0

快速排序：from  http://www.cnblogs.com/Mainz/archive/2008/04/22/1165429.html 时间比原生的少

private void Swrap(int[] v, int index1, int index2)
    {
        int temp = v[index1];
        v[index1] = v[index2];
        v[index2] = temp;
    }
     
    /// <summary>
    /// Split into left and right sub-table
    /// </summary>
    private int PivotIndex(int[] v, int first, int last)
    {
        if (last == first)
        {
            return last;
        }
        if (last - first == 1)
        {
            return first;
        }
        int mid = (first + last) / 2;
        int midVal = v[mid];
     
        //Swap v[first] v[mid]
        Swrap(v, first, mid);
        int scanA = first + 1;
        int scanB = last - 1;
        for (; ; )
        {
            while (scanA <= scanB && v[scanA] < midVal)
            {
                scanA++;
            }
            while (scanB > first && midVal <= v[scanB])
            {
                scanB--;
            }
            if (scanA >= scanB)
            {
                break;
            }
            Swrap(v, scanA, scanB);
            scanA++;
            scanB--;
        }
        Swrap(v, first, scanB);
        return scanB;
     
    }
    public void Sort(int[] v, int first, int last)
    {
        if (last - first <= 1)
        {
            return;
        }
        if (last - first == 2)
        {
            //Sub-table contains two elements
            if (v[first] > v[last - 1])
            {
                Swrap(v, first, last - 1);
            }
            return;
        }
        else
        {
            int pivotIndex = PivotIndex(v, first, last);
            Sort(v, first, pivotIndex);
            Sort(v, pivotIndex + 1, last);
        }
    }

4.HashMap排序

HashMap   map   =   new   HashMap();   
             map.put("0201",   "0201");   
             map.put("01",   "01");   
             map.put("0304",   "0304");   
             map.put("0101",   "0101");  
             Object[]   key   =  map.keySet().toArray();   
             Arrays.sort(key);  
             for   (int   i   =   0;   i   <   key.length;   i++)   {   
                     System.out.println(map.get(key[i]));   
             }

\-----------------------------------------------------------------------

使用Collectons工具类排序-----针对list类型排序----现将数据entrySet放入List

Map hashMap = new HashMap();
    List arrayList = new ArrayList(hashMap.entrySet());
    Collections.sort(arrayList, new Comparator() {
       public int compare(Object o1, Object o2) {
        Map.Entry obj1 = (Map.Entry) o1;
        Map.Entry obj2 = (Map.Entry) o2;
        return (obj1.getKey()).toString().compareTo(obj2.getKey());
       }
      });

//  将HASHMAP中的数据排序-------------------------------------------

for (Iterator iter = arrayList.iterator(); iter.hasNext();) {
       Map.Entry entry = (Map.Entry) iter.next();
       String     key = (String)entry.getKey();
       ..........
      }

综合排序实例

Map<String, Integer> map = new HashMap<String, Integer>();
    map.put("d", 2);
    map.put("c", 1);
    map.put("b", 1);
    map.put("a", 3);
    
    List<Map.Entry<String, Integer>> infoIds =
        new ArrayList<Map.Entry<String, Integer>>(map.entrySet());
    
    //排序前
    for (int i = 0; i < infoIds.size(); i++) {
        String id = infoIds.get(i).toString();
        System.out.println(id);
    }
    //d 2
    //c 1
    //b 1
    //a 3
    
    //排序
    Collections.sort(infoIds, new Comparator<Map.Entry<String, Integer>>() {   
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {      
            //return (o2.getValue() - o1.getValue()); 
            return (o1.getKey()).toString().compareTo(o2.getKey());
        }
    }); 
    
    //排序后
    for (int i = 0; i < infoIds.size(); i++) {
        String id = infoIds.get(i).toString();
        System.out.println(id);
    }
    //根据key排序
    //a 3
    //b 1
    //c 1
    //d 2
    //根据value排序
    //a 3
    //d 2
    //b 1
    //c 1

**改进=号的排序！！！！！**

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    public class SortMap {
    	public static void main(String[] args) {
    		Map<String, Integer> map = new HashMap<String, Integer>();
    		map.put("d", 2);
    		map.put("c", 1);
    		map.put("b", 1);
    		map.put("a", 3);
    
    		List<Map.Entry<String, Integer>> infoIds =
    		    new ArrayList<Map.Entry<String, Integer>>(map.entrySet());
    
    		//排序前
    		for (int i = 0; i < infoIds.size(); i++) {
    		    String[] id = infoIds.get(i).toString().split("=");
    		    System.out.println(id[0]+" "+id[1]);
    		}
    		//d 2
    		//c 1
    		//b 1
    		//a 3
    
    		//排序
    		Collections.sort(infoIds, new Comparator<Map.Entry<String, Integer>>() {   
    		    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {      
    		        return (o2.getValue() - o1.getValue()); //返回的值！！！！！！！！！！！！经典
    		        //return (o1.getKey()).toString().compareTo(o2.getKey());
    		    }
    		}); 
    
    		//排序后---=的形式
    //		for (int i = 0; i < infoIds.size(); i++) {
    //		    String id = infoIds.get(i).toString();
    //		    System.out.println(id);
    //		}
    		for (int i = 0; i < infoIds.size(); i++) {
    		    String[] id = infoIds.get(i).toString().split("=");
    		    System.out.println(id[0]+" "+id[1]);
    		}
    		//根据key排序
    		//a 3
    		//b 1
    		//c 1
    		//d 2
    		//根据value排序
    		//a 3
    		//d 2
    		//b 1
    		//c 1
    	}
    
    
    }

[Center]: /images/20220720/3bcd208a65dc4424b54e22fcaf9429f6.png