java:快速排序算法与冒泡排序算法

Java:快速排序算法与冒泡算法

首先看下,冒泡排序算法与快速排序算法的效率:

如下的是main方法:

/**
  * 
 * @Description: 
 * @author:cuiyaonan2000@163.com
 * @date 2014年11月5日 下午1:02:10
  */
 public static void main(String[] args) {
  //快速排序算法测试
  int[] qArray = new int[100000];
  for (int i = 0; i < 100000; i++){
   qArray[i] = (int) (Math.random() * 100000);
  }
  long beforeQ = System.currentTimeMillis();
  quickSort(qArray, 0, qArray.length-1);
  System.out.println("快速排序运行时间:" + (System.currentTimeMillis() - beforeQ));
  
  //冒泡排序算法测试
  int[] bArray = new int[100000];
  for (int i = 0; i < 100000; i++){
   bArray[i] = (int) (Math.random() * 100000);
  }
  long beforeB = System.currentTimeMillis();
  bubble(bArray);
  System.out.println("冒泡排序运行时间:" + (System.currentTimeMillis() - beforeB));
 }

在一个有100000 个数字的数组中排序结果如下:

如下的是大家耳熟能详的冒泡算法(关于冒泡就不多说了):

     

/**
  * 
 * @Description: 
 * @author:cuiyaonan2000@163.com
 * @date 2014年11月5日 下午1:00:32
  */
 public static void bubble(int[] data) {
  for (int i = 0; i < data.length - 1; i++) {
   for (int j = i + 1; j < data.length; j++)
    if (data[i] > data[j]) {
     int temp = data[j];
     data[j] = data[i];
     data[i] = temp;
    }
  }
 }

 

先说下关于快速排序算法的思路:

1. 选取数组第一个数字,作为key.并设置变量i为0,j为数组长度.

2. 从数组最后一位开始向前找,找什么呢?找比key小的数字(不能等于),并记录下坐标j.限制条件是,在向前找的过程中如果一直没找到比key小的数值,就在i