当前位置：首页 -> AI编程基础 -> JAVA

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

2014-11-24 08:22:28 · 作者: · 浏览: 1
标签: Java 快速 排序 sdut 1196 为例
Java中，Arrays.sort()静态方法就是利用的快速排序，（看到网上有的说用的归并排序，测试了下，跟自己写的快速排序消耗的时间和空间都一样，所以确定是快速排序），对类的集合排序，需要实现Comparable接口，（类似C++ STL中sort函数需要的小于号）。初学Java集合，记录一下。初学者。。下面是调用Arrays.sort()和自己实现的泛型MySort()的两种写法：
首先是一个内部类：（上面链接的题目要求） 
public static class Data implements Comparable {  
    private int num;  
    private int step;  
  
    @Override  
    public int compareTo(Object arg0) {  
        Data other = (Data)arg0;  
        if(other.num > this.num)  
            return -1;  
        if(other.num == this.num)  
            return 0;  
        return 1;  
    }  
}   
  
 
 
  
 

   
 
 
 

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

   
 
 
 

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

    
  
private static Scanner input;  
      
public static void main(String[] args) {  
    input = new Scanner(System.in);  
    Data[] tmp = new Data[10];  
    for(int i = 0; i < 10; i++) {  
        tmp[i] = new Data();  
        tmp[i].num = input.nextInt();  
        tmp[i].step = i + 1;  
    }  
    Arrays.sort(tmp);  
    //下面的代码只是为了实现题目要求的输出格式  
    for(int i = 0; i < 9; i++) {  
        System.out.print(tmp[i].num + " ");  
    }  
    System.out.println(tmp[9].num);  
    for(int i = 0; i < 9; i++) {  
        System.out.print(tmp[i].step + " ");  
    }  
    System.out.println(tmp[9].step);  
}  
 
  
 






 
 
 
 

   
 
 
 

   
 
 
 

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

   
 
 
 

    
  
private static > void quick_sort(T[] s, int l, int r) {  
    if(l >= r) return;  
    int i = l, j = r;  
    T x = s[l];  
    while(i < j) {  
        while(i < j && s[j].compareTo(x) >= 0)  
            j--;  
        if(i < j)  
            s[i++] = s[j];  
        while(i < j && s[i].compareTo(x) < 0)  
            i++;  
        if(i < j)  
            s[j--] = s[i];  
    }  
    s[i] = x;  
    quick_sort(s, l, i-1);  
    quick_sort(s, i+1, r);  
}  
      
private static > void MySort(T[] data) {  
    quick_sort(data, 0, data.length-1);  
}  
 
  
 
 
 
 
 

   
 
 
 

  有不足之处谢谢指出！