大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > Java 泛型快速排序 以sdut 1196为例

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

关键词:Java泛型排序Java泛型快速排序以sdut11  阅读(647) 赞(13)

[摘要]本文主要是对Java 泛型快速排序 以sdut 1196为例的讲解,希望对大家学习Java 泛型快速排序 以sdut 1196为例有所帮助。

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

  首先是一个内部类:(上面链接的题目要求)

  public static class Data implements Comparable<Object> {

  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 <T extends Comparable<Object》 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 <T extends Comparable<Object》 void MySort(T[] data) {

  quick_sort(data, 0, data.length-1);

  }

  有不足之处谢谢指出!



相关评论