Java 泛型快速排序以sdut 1196为例

oj链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1196

Java中，Arrays.sort()静态方法就是利用的快速排序，（看到网上有的说用的归并排序，测试了下，跟自己写的快速排序消耗的时间和空间都一样，所以确定是快速排序），对类的集合排序，需要实现Comparable接口，（类似C++ STL中sort函数需要的小于号）。初学Java集合，记录一下。初学者。。下面是调用Arrays.sort()和自己实现的泛型MySort()的两种写法：

首先是一个内部类：（上面链接的题目要求）

 1 public static class Data implements Comparable<Object> {
 2     private int num;
 3     private int step;
 4 
 5     @Override
 6     public int compareTo(Object arg0) {
 7         Data other = (Data)arg0;
 8         if(other.num > this.num)
 9             return -1;
10         if(other.num == this.num)
11             return 0;
12         return 1;
13     }
14 }

Data 内部类

话说内部类不需要get和set方法。。

然后是需要提交的类中的main方法

 1 private static Scanner input;
 2     
 3 public static void main(String[] args) {
 4     input = new Scanner(System.in);
 5     Data[] tmp = new Data[10];
 6     for(int i = 0; i < 10; i++) {
 7         tmp[i] = new Data();
 8         tmp[i].num = input.nextInt();
 9         tmp[i].step = i + 1;
10     }
11     Arrays.sort(tmp);
12     //下面的代码只是为了实现题目要求的输出格式
13     for(int i = 0; i < 9; i++) {
14         System.out.print(tmp[i].num + " ");
15     }
16     System.out.println(tmp[9].num);
17     for(int i = 0; i < 9; i++) {
18         System.out.print(tmp[i].step + " ");
19     }
20     System.out.println(tmp[9].step);
21 }

main方法

然后是自己写的泛型MySort方法，依旧没有异常处理，ACM用的。。

 1 private static <T extends Comparable<Object>> void quick_sort(T[] s, int l, int r) {
 2     if(l >= r) return;
 3     int i = l, j = r;
 4     T x = s[l];
 5     while(i < j) {
 6         while(i < j && s[j].compareTo(x) >= 0)
 7             j--;
 8         if(i < j)
 9             s[i++] = s[j];
10         while(i < j && s[i].compareTo(x) < 0)
11             i++;
12         if(i < j)
13             s[j--] = s[i];
14     }
15     s[i] = x;
16     quick_sort(s, l, i-1);
17     quick_sort(s, i+1, r);
18 }
19     
20 private static <T extends Comparable<Object>> void MySort(T[] data) {
21     quick_sort(data, 0, data.length-1);
22 }

MySort方法

有不足之处谢谢指出！

Java 泛型快速排序 以sdut 1196为例

Java 泛型快速排序以sdut 1196为例