package com.cucu.test;

/**
 * @author http://www. <a href=mailto:cg@
 * @version 1.0
 */
public class Sort {

  public void swap(int a[], int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
  }

  public int partition(int a[], int low, int high) {
    int pivot, p_pos, i;
    p_pos = low;
    pivot = a[p_pos];
    for (i = low + 1; i <= high; i++) {
      if (a[i] > pivot) {
        p_pos++;
        swap(a, p_pos, i);
      }
    }
    swap(a, low, p_pos);
    return p_pos;
  }

  public void quicksort(int a[], int low, int high) {
    int pivot;
    if (low < high) {
      pivot = partition(a, low, high);
      quicksort(a, low, pivot - 1);
      quicksort(a, pivot + 1, high);
    }

  }

  public static void main(String args[]) {
    int vec[] = new int[] { 37, 47, 23, -5, 19, 56 };
    int temp;
    //选择排序法(Selection Sort)
    long begin = System.currentTimeMillis();
    for (int k = 0; k < 1000000; k++) {
      for (int i = 0; i < vec.length; i++) {
        for (int j = i; j < vec.length; j++) {
          if (vec[j] > vec[i]) {
            temp = vec[i];
            vec[i] = vec[j];
            vec[j] = temp;
          }
        }

      }
    }
    long end = System.currentTimeMillis();
    System.out.println("选择法用时为：" + (end - begin));
    //打印排序好的结果
    for (int i = 0; i < vec.length; i++) {
      System.out.println(vec[i]);
    }
    //  冒泡排序法(Bubble Sort)
    begin = System.currentTimeMillis();
    for (int k = 0; k < 1000000; k++) {
      for (int i = 0; i < vec.length; i++) {
        for (int j = i; j < vec.length - 1; j++) {
          if (vec[j + 1] > vec[j]) {
            temp = vec[j + 1];
            vec[j + 1] = vec[j];
            vec[j] = temp;
          }
        }

      }
    }
    end = System.currentTimeMillis();
    System.out.println("冒泡法用时为：" + (end - begin));
    //打印排序好的结果
    for (int i = 0; i < vec.length; i++) {
      System.out.println(vec[i]);
    }

    //插入排序法(Insertion Sort)
    begin = System.currentTimeMillis();
    for (int k = 0; k < 1000000; k++) {
      for (int i = 1; i < vec.length; i++) {
        int j = i;
        while (vec[j - 1] < vec[i]) {
          vec[j] = vec[j - 1];
          j--;
          if (j <= 0) {
            break;
          }
        }
        vec[j] = vec[i];
      }
    }
    end = System.currentTimeMillis();
    System.out.println("插入法用时为：" + (end - begin));
    //打印排序好的结果
    for (int i = 0; i < vec.length; i++) {
      System.out.println(vec[i]);
    }

    //快速排序法(Quick Sort)

    Sort s = new Sort();
    begin = System.currentTimeMillis();
    for (int k = 0; k < 1000000; k++) {
      s.quicksort(vec, 0, 5);
    }
    end = System.currentTimeMillis();
    System.out.println("快速法用时为：" + (end - begin));
    //打印排序好的结果
    for (int i = 0; i < vec.length; i++) {
      System.out.println(vec[i]);
    }
  }

}
以下是运行结果：
选择法用时为：234
56
47
37
23
19
-5
冒泡法用时为：172
56
47
37
23
19
-5
插入法用时为：78
56
47
37
23
19
-5
快速法用时为：297
56
47
37
23
19
-5

经典

以上算法都比不上Arrays.sort(). Arrays.sort()的效率是最高的

不过自己知底层代码还是有好处的。至少能够深入理解还有懂得这原理

有些大点的公司就喜欢玩些让你写算法啊之类的，所以知道点要比较好

System.currentTimeMillis()这方法咋用呀！

帮你查了一下API：System.currentTimeMillis()返回当前时间与协调世界时 1970 年 1 月 1 日午夜之间的时间差（以毫秒为单位测量）。这里是用于计算程序的运行时间

如果不是到大公司面试，我建议大家还是选用Arrays.sort()方法来排序

我用以下程序做过测试
import java.util.*;

public class Sort2 {

 
  public static void main(String args[]) {
    int vec[] = new int[10000];
    Random ran = new Random();
    for (int i=0;i<10000;i++) {
            int value = ran.nextInt(10000)+1;
            vec[i]= value;
    }

    System.out.println("Before sort:");
    for (int i = 0; i < vec.length; i++) {
             System.out.println(vec[i]);
    }  
  
    long begin = System.currentTimeMillis();
    Arrays.sort(vec);
    long end = System.currentTimeMillis();
    System.out.println("Arrays Sort：" + (end - begin));
 
    System.out.println("After sort:");
    for (int i = 0; i < vec.length; i++) {
             System.out.println(vec[i]);
    }
   
  }

}

对100000个元素的数组排序，用时32
对1000000个元素的数组排序，用时234
对10000000个元素的数组排序，用时2703


[ 本帖最后由 lampeter123 于 2009-10-31 15:17 编辑 ]

收藏了

hao