9.排序算法

1.冒泡排序

基本介绍：

  冒泡排序的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），一次比较相邻元素的值，如果发现逆序，使较大的元素逐渐从前向后移动。

因为在排序的过程中，各元素不断的接近自己的位置，如果一趟比较下来没有进行任何交换，就说明序列有序。因此要在排序过程中设置一个标志flag，判断元素是否进行交换，从而减少不必要的比较。(后期优化)

示例：

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {11,3, 9, -1, 10, -2};
        int count=0;
        //冒泡排序
        //第一层for循环是循环次数：例如5个数，总共循环5-1=4次
        System.out.println("原始数据： "+Arrays.toString(arr));
        System.out.println("开始排序------");
        for (int i = 0; i < arr.length - 1; i++) {
            //第二层for循环，是比较次数
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int num=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1] = num;
                }
                System.out.println("第"+(count++)+"次排序："+Arrays.toString( arr));
            }
            System.out.println("内层排序结束---");
        }
    }
}

输出：

原始数据： [11, 3, 9, -1, 10, -2]
开始排序------
第0次排序：[3, 11, 9, -1, 10, -2]
第1次排序：[3, 9, 11, -1, 10, -2]
第2次排序：[3, 9, -1, 11, 10, -2]
第3次排序：[3, 9, -1, 10, 11, -2]
第4次排序：[3, 9, -1, 10, -2, 11]
内层排序结束---
第5次排序：[3, 9, -1, 10, -2, 11]
第6次排序：[3, -1, 9, 10, -2, 11]
第7次排序：[3, -1, 9, 10, -2, 11]
第8次排序：[3, -1, 9, -2, 10, 11]
内层排序结束---
第9次排序：[-1, 3, 9, -2, 10, 11]
第10次排序：[-1, 3, 9, -2, 10, 11]
第11次排序：[-1, 3, -2, 9, 10, 11]
内层排序结束---
第12次排序：[-1, 3, -2, 9, 10, 11]
第13次排序：[-1, -2, 3, 9, 10, 11]
内层排序结束---
第14次排序：[-2, -1, 3, 9, 10, 11]
内层排序结束---

结论：发现每次排序都会把最大数放在结尾处！

优化，先看案例：

如果给int arr[] = {1, 2, 3, 5, 4}排序呢
输出：
    原始数据： [1, 2, 3, 5, 4]
    开始排序------
    第0次排序：[1, 2, 3, 5, 4]
    第1次排序：[1, 2, 3, 5, 4]
    第2次排序：[1, 2, 3, 5, 4]
    第3次排序：[1, 2, 3, 4, 5]
    内层排序结束---
    第4次排序：[1, 2, 3, 4, 5]
    第5次排序：[1, 2, 3, 4, 5]
    第6次排序：[1, 2, 3, 4, 5]
    内层排序结束---
    第7次排序：[1, 2, 3, 4, 5]
    第8次排序：[1, 2, 3, 4, 5]
    内层排序结束---
    第9次排序：[1, 2, 3, 4, 5]
    内层排序结束---

发现3-9次的排序均一样的，这就是优化的点！
    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 5, 4};
        int count = 0;
        //冒泡排序
        //第一层for循环是循环次数：例如5个数，总共循环5-1=4次
        System.out.println("原始数据： " + Arrays.toString(arr));
        System.out.println("开始排序------");
        //重点1：表示是否进行过交换
        boolean flag = false;
        for (int i = 0; i < arr.length - 1; i++) {
            //第二层for循环，是比较次数
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int num = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = num;
                    //重点2:如果发生交换，该字段置为true；
                    flag = true;
                }
                System.out.println("第" + (count++) + "次排序：" + Arrays.toString(arr));
            }
            //内层排序结束后，判断这个字段
            //没有进行过交换，直接退出！
            if (!flag) {
                break;
            } else {
                //flag=true:进行过交换，这里需要重置下flag，方便下次判断！
                flag = false;
            }
            System.out.println("内层排序结束---");
        }
    }
    
输出：发现减少了3次排序
    原始数据： [1, 2, 3, 5, 4]
    开始排序------
    第0次排序：[1, 2, 3, 5, 4]
    第1次排序：[1, 2, 3, 5, 4]
    第2次排序：[1, 2, 3, 5, 4]
    第3次排序：[1, 2, 3, 4, 5]
    内层排序结束---
    第4次排序：[1, 2, 3, 4, 5]
    第5次排序：[1, 2, 3, 4, 5]
    第6次排序：[1, 2, 3, 4, 5]
 内层排序无法减少，即3-6的排序是无法精简的，因为内层排序是元素一位一位去比较，根本不知道后面元素的大小，两次比较结果相同，并不能说明已经有序：如
 本以为这么修改：
         //上次排序结果
        String str="";
        for (int i = 0; i < arr.length - 1; i++) {
            //第二层for循环，是比较次数
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int num = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = num;
                }
                //重点1：比较上次移动和这次的字符串是否一样
                if (str.equals(Arrays.toString(arr))) {
                    break;
                }
               str=Arrays.toString(arr);
                System.out.println("第"+(count++)+"次排序:"+str);
            }
            System.out.println("内层排序结束---");
        }
输出;
原始数据： [1, 2, 3, 5, 4]
开始排序------
第0次排序:[1, 2, 3, 5, 4]
内层排序结束---
    
结论：    
这时还没有有序，内层排序无法减少优化！

原文地址：http://www.cnblogs.com/wmd-l/p/16924692.html