黑马程序员技术交流社区

标题: 数组排序 [打印本页]

作者: yin1031468524 时间: 2013-6-4 12:14
标题: 数组排序
本帖最后由 yin1031468524 于 2013-6-4 17:52 编辑

随机产生一个整型数组如 int[] array = {6,6,5,5,1,1,2,2,2,3,3,4,4,4};
给这个数组 ,按照出现次数排序，出现次数越多，拍的越靠前，如出现次数一样则，比较两个数大小，大的拍前
求大神指导~

作者: 胡晓思 时间: 2013-6-4 12:45
楼主int[]数组里貌似定义了 double

作者: 坚持远方 时间: 2013-6-4 13:02
应该先对于数组中出现的数字的次数记录一下，到最后根据次数进行排序，你先看一下吧

public static void main(String[] args) {
      i int[] array = {6,6.5,5.1,1,2,2,3,4,4,4}；
      Arrays.sort(array);// 给数组排序
      int count=0;
      int tmp=array[0];
      Map map=new HashMap();
      for(int i=0; i < array.length; i++) {
         if(tmp != array[i]) {
            tmp=array[i];
            count=1;
         } else {
            count++;
         }
         map.put(array[i], count);
      }
      map=sortByValue(map);
      Set<Integer> key = map.keySet();
      for (Iterator it = key.iterator(); it.hasNext();) {
         Integer s = (Integer) it.next();
         System.out.println(s+"出现了"+map.get(s));
      }
}

public static Map sortByValue(Map map) {
      List list=new LinkedList(map.entrySet());
      Collections.sort(list, new Comparator() {
         // 将链表按照值得从小到大进行排序
         public int compare(Object o1, Object o2) {
            return ((Comparable)((Map.Entry)(o2)).getValue

()).compareTo(((Map.Entry)(o1)).getValue());
         }
      });
      Map result=new LinkedHashMap();
      for(Iterator it=list.iterator(); it.hasNext();) {
         Map.Entry entry=(Map.Entry)it.next();
         result.put(entry.getKey(), entry.getValue());
      }
      return result;
}

作者: 胡晓思 时间: 2013-6-4 13:31
本帖最后由胡晓思于 2013-6-4 13:44 编辑

//基于技术排序的原理,使用一个计数数组,数组脚标就是被排元素,数组元素是个数,按照要求取出数据,重新赋给被排数组就可以了楼主觉得如何不过此方法只能排不同整数比较小的不过有点是性能较好,特别是重复较多的小整数排序
import java.util.Arrays;
public class temp {
public static void main(String[] args) {
int[] arr = { 6, 6, 5, 5, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4 };
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
int[] num = new int[10];
for (int i = 0; i < arr.length; i++) {
num[arr[i]]++;
}
for (int a = 0; a < arr.length;) {
for (int i = num.length - 1; i > 0; i--) {
if (num[i] == getMax(num)) {
for (int j = 0; j < getMax(num); j++) {
arr[a++] = i;
}
num[i] = 0;
break;
}
}
}
}
public static int getMax(int[] arr) {
int max = 0;
for (int a : arr) {
if (a > max)
max = a;
}
return max;
}
}

复制代码

作者: 胡晓思 时间: 2013-6-4 13:49
输出结果:[4, 4, 4, 2, 2, 2, 6, 6, 5, 5, 3, 3, 1, 1]

作者: 小羽天空 时间: 2013-6-4 16:32
看了很久楼上的代码，才弄明白它的原理，所以特意附加注释帮助lz理解：
import java.util.Arrays;

public class A{

   public static void main(String[] args) {

            int[] arr = { 6,5, 6, 5, 5, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4,7,7 };//自定义一个数组

            sort(arr);//调用sort函数

            System.out.println(Arrays.toString(arr));//打印排列好的数组

   }

   public static void sort(int[] arr) {

            int[] num = new int[10];//定义一个数组存放arr元数的个数

            for (int i = 0; i < arr.length; i++) {

                  num[arr[i]]++;//增加数据，即arr相同元数中的个数

            }

            for (int a = 0; a < arr.length;) {

                  for (int i = num.length - 1; i > 0; i--) {//倒叙是为了使他从大到小排列

                           if (num[i] == getMax(num)) //判断元数的次数
                           {

                                    for (int j = 0; j < getMax(num); j++) //重新排列arr
                                    {

                                          arr[a++] = i;

                                    }

                                    num[i] = 0;//排好序的数组清0，是他不影响下次元数的比较

                                    break;

                           }


                  }

            }

   }

   public static int getMax(int[] arr) {//创建函数筛选数组中最在元数，本题为次数最大的

            int max = 0;

            for (int a : arr) {//使用高级for循环，从arr【0】到arr【arr。length】进行比较

                  if (a > max)

                           max = a;

            }

            return max;//返回最大值

   }

}

作者: 胡晓思 时间: 2013-6-4 18:01

小羽天空发表于 2013-6-4 16:32
看了很久楼上的代码，才弄明白它的原理，所以特意附加注释帮助lz理解：
import java.util.Arrays;

谢谢了不好意思忘记加注释了

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2