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

 

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

 

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

 

 

 

 

 

      /**

        *

       * @Description:

       * @author:[e-mail]

       * @date 2014年11月5日 下午1:00:32

        */

 public static void main(String[] args) {

 

           //快速排序算法测试

 

           int[] qArray = newint[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 = newint[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:[e-mail]

       * @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<j的时候停止(如果没有找到j就做减一操作继续找).如果找到了就将 数组[j] 与数组[i]的值对换并结束.

3. 从数组第一位开始向后找,找什么呢?找比key大的数字(不能等于),并记录下坐标i.限制条件是,在向前找的过程中如果一直没找到比key大的数值,就在i<j的时候停止(如果没有找到i就做加一操作继续找).如果找到了就将 数组[j] 与数组[i]的值对换并结束.

4. 完成如上的操作,打印输出数组发现:数据变得相对有序了,就是在数组中key值坐标前面的都是小于key的,key值坐标后面的都是大于key值得.

5. 所以大家明白了:将以key值为坐标的数组拆分成2个数组,分别去执行123步骤操作,最终就会产生一个有序数组

 

      /**

        *

       * @Description:

       * @author:[e-mail]

       * @date 2014年11月5日 下午1:00:32

        */

 public static void quickSort(int[] array,int begin,int end){

 

           int theKey = array[begin];   //设置关键值

 

           int i = begin;

 

           int j = end;

 

           while(true){

 

                 while(i<j && array[j] >= theKey)   //从后面找到一个比关键之小的数字坐标

 

                      j--  ;

 

                 if(i<j){  //交换

 

                      int temp = array[j];

 

                      array[j] = array[i];

 

                      array[i] = temp;

 

                 }else{

 

                      break;

 

                 }

 

                 while(i<j && array[i] <= theKey)   //从前面找到一个比关键之大的数字坐标

 

                      i++;

 

                 if(i<j){ //交换

 

                      int temp = array[j];

 

                      array[j] = array[i];

 

                      array[i] = temp;

 

                 }else{

 

                      break;

 

                 }

 

           }

 

          

 

           if(--i > begin ){//这个表示一直找到 被拆分的数组中只有一个值.否则递归调用

 

                 quickSort(array,begin,i);

 

           }

 

           if(++j< end){ //这个表示一直找到 被拆分的数组中只有一个值.否则递归调用

 

                 quickSort(array,j,end);

 

           }

 

      }