首页 > 代码库 > 貌似基数排序

貌似基数排序

2024-08-02 23:31:46   214人阅读

如给定数组{1,3,51,5,512,671,9,67}，设计程序，输出{9,671,67,512,51,5,3,1}

基本思想是给每一位数字定权重，然后使用如W[671] = 6 * w1 + 7 * w2 + 1 * w3;W的个数由数组中位数最长的数字决定。由数组中数字对应的权值来排序即可

程序如下：

 1 import java.util.*; 2 import java.math.*; 3 public class Hello { 4    public static List<Integer> sort(int[] arr) 5    { 6        String[] strs = new String[arr.length]; 7        int curLen = 0, maxLen = 0; 8        for(int i = 0; i < strs.length; i++) 9        {10            strs[i] = String.valueOf(arr[i]);11            curLen = strs[i].length();12            if(curLen > maxLen)13                maxLen = curLen;14        }15        HashMap<String,Integer> hm = new HashMap<String,Integer>();16        for(int i = 0; i < strs.length; i++)17        {18            hm.put(strs[i],0);19            for(int j = 0; j < strs[i].length(); j++)20            {21                hm.put(strs[i],hm.get(strs[i]) + (strs[i].charAt(j) - ‘0‘)*(int)Math.pow(10,maxLen - j));22            }23        }24        List<Map.Entry<String,Integer>> list = new ArrayList<Map.Entry<String,Integer>>();25        list.addAll(hm.entrySet());26        ValueComparator vc = new ValueComparator();27        Collections.sort(list,vc);28        List<Integer> intList = new ArrayList<Integer>();29        for(Iterator<Map.Entry<String,Integer>> it = list.iterator();it.hasNext();)30        {31             intList.add(Integer.valueOf(it.next().getKey()));   32        }33            34        return intList;35    }36     37    public static void main(String[] args) {38        int[] arr = {11,1,12,23,24,22,456,467,567};39        List<Integer> a =sort(arr);40        System.out.println(a);41    }42 }43 44 class ValueComparator implements Comparator<Map.Entry<String,Integer>>45 {46     public int compare(Map.Entry<String,Integer> mp1,Map.Entry<String,Integer> mp2)47     {48         return mp2.getValue() - mp1.getValue();49     }50 }

 

貌似基数排序


联系
我们