首页 > 代码库 > 快速排序 VS compare排序

快速排序 VS compare排序

2024-09-16 14:50:22   216人阅读

为了方便  ，我把bean写成了内部类

测试结论 ，快速排序吊打compare排序 ,可以自行测试

 1     //测试调用
 2     public static void main(String[] args) {
 3         List<Student> list = new ArrayList<Student>();
 4         new test().add(list);
 5         //记录旧数据  确定俩次排序使用的是同一数据
 6         List<Student> stus = new ArrayList<Student>();
 7         stus = list;
 8         
 9         long aa = new Date().getTime();
10         quickSort(list, 0, list.size() - 1);
11         System.out.println("快速排序" + (new Date().getTime() - aa));
12 
13         System.out.println();
14         
15         aa = new Date().getTime();
16         Collections.sort(stus, new IndexComparator());
17         System.out.println("compare排序" + (new Date().getTime() - aa));
18     }

 

1 //创建100w条学生
2     public void add(List<Student> list) {
3         while (list.size() < 1000000) {
4             list.add(new Student((new Random().nextInt(1000000) + 1), ""));
5         }
6     }
 1 //快速排序
 2     public static void quickSort(List<Student> data, int left, int right) {
 3         Student temp = new Student();
 4         int f, rtemp, ltemp;
 5         ltemp = left;
 6         rtemp = right;
 7         f = data.get((left + right) / 2).getCount();
 8         while (ltemp < rtemp) {
 9             while (data.get(ltemp).getCount() < f) {
10                 ++ltemp;
11             }
12             while (data.get(rtemp).getCount() > f) {
13                 --rtemp;
14             }
15             if (ltemp <= rtemp) {
16                 temp = data.get(ltemp);
17                 data.set(ltemp, data.get(rtemp));
18                 data.set(rtemp, temp);
19                 --rtemp;
20                 ++ltemp;
21             }
22         }
23         if (left == rtemp) {
24             ltemp++;
25         }
26         if (left < rtemp) {
27             quickSort(data, rtemp + 1, right);
28         }
29         if (ltemp < right) {
30             quickSort(data, rtemp + 1, right);
31         }
32     }
 1     /**
 2      * compare排序
 3      */
 4     static class IndexComparator implements Comparator<Student> {
 5 
 6         @Override
 7         public int compare(Student o1, Student o2) {
 8             Integer sort1 = o1.getCount();
 9             Integer sort2 = o2.getCount();
10             return sort1.compareTo(sort2);
11         }
12     }

 

实体Student

技术分享 
 1 static class Student {
 2         private int count;
 3 
 4         private String name;
 5 
 6         public int getCount() {
 7             return count;
 8         }
 9 
10         public Student() {
11             super();
12             // TODO Auto-generated constructor stub
13         }
14 
15         public Student(int count, String name) {
16             super();
17             this.count = count;
18             this.name = name;
19         }
20 
21         public void setCount(int count) {
22             this.count = count;
23         }
24 
25         public String getName() {
26             return name;
27         }
28 
29         public void setName(String name) {
30             this.name = name;
31         }
32     }
View Code

 

快速排序 VS compare排序


联系
我们