冒泡排序，冒泡性能优化--java实现

冒泡排序说明：

一次比较两个元素，如果他们的顺序错误就把他们交换过来。

重复地进行直到没有再需要交换，也就是说已经排序完成。

越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下:

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

简单的冒泡排序代码：

import java.util.Arrays;

/**

 * 实现冒泡排序

 * @author dell

 *

 */

public class BubbleSort {

    public static void main(String[] args) {

        int[] arr = {1,200,19,55,10,22,3,7};

        //API实现

        Arrays.sort(arr);

        System.out.println(Arrays.toString(arr));

        //冒泡实现

        int temp;

        for(int i =0;i<arr.length-1;i++){

            for(int j = 0;j<arr.length-1-i;j++){

                if(arr[j]>arr[j+1]){

                    temp = arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=temp;

                }

            }

        }

        System.out.println(Arrays.toString(arr));

    }

}

冒泡排序的性能分析和算法优化（外层循环优化）

问题：

有的冒泡经过第一轮的交换已经是有序的了，如：2 1 3 4。数据越多的时候越慢，非常不适合大数据的排序

解决办法

如果用一个flag来判断一下，当前数组是否已经有序，如果有序就退出循环，这样可以明显的提高冒泡排序的性能。

package bubbleSort;

import java.util.Arrays;

import org.junit.Test;

/**

 * 冒泡排序的性能分析和算法优化（外层循环优化）

 * @author dell

 *

 */

public class BubbeSort02 {

    @Test

    public void test1(){

        boolean flag = true;

        int[] arr = {2,1,3,4,5};

        int temp;

        for (int i = 0; i < arr.length-1; i++) {

            for (int j = 0; j < arr.length-1-i; j++) {

                if(arr[j]>arr[j+1]){

                    temp=arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=temp;

                    flag=false;

                }

            }

            if(!flag){

                //没有发生交换则退出循环；

                break;

            }

        }

        System.out.println(Arrays.toString(arr));

    }

}

冒泡排序第二种优化（内层循环优化）

    /**

     * 冒泡排序的性能分析和算法优化（内层循环优化）

     */

    @Test

    public void test2(){

        int[] arr = {22,1,10,5};

        //标记最后一次交换的位置

        for (int i = 0; i < arr.length-1; i++) {

            int flag = 0;

            int temp;

            for (int j = 0; j < arr.length-i-1; j++) {

                if(arr[j]>arr[j+1]){

                    temp=arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=temp;

                    //当位置发生改变，flag的值就发生变化

                    flag=1;

                }

            }

            //判断标志位flag有没有发生变化，没有就直接结束内层循环

            if(flag==0){

                return;

            }

        }

        System.out.println(Arrays.toString(arr));

    }

}

参考链接

http://blog.csdn.net/pzhtpf/article/details/7560294

http://www.jianshu.com/p/ffcf5f97bc36

巴特西