bubble_sort

/*以从小到大排序为例，每一轮排序就找出未排序序列中最大值放在最后
设数组的长度为N：
（1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。
（2）这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
（3）N=N-1，如果N不为0就重复前面二步，否则排序完成。

```
*/

//没有任何优化的冒泡排序
// Java program for implementation of Bubble Sort 
class BubbleSort 
{ 
    void bubbleSort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 0; i < n-1; i++) 
            for (int j = 0; j < n-i-1; j++) 
                if (arr[j] > arr[j+1]) 
                { 
                    // swap arr[j+1] and arr[j] 
                    int temp = arr[j]; 
                    arr[j] = arr[j+1]; 
                    arr[j+1] = temp; 
                } 
    } 
    /* Prints the array */ 
    void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i] + " "); 
        System.out.println(); 
    } 
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BubbleSort ob = new BubbleSort(); 
        int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
        ob.bubbleSort(arr); 
        System.out.println("Sorted array"); 
        ob.printArray(arr); 
    } 
} 
/*```
下面开始考虑优化，如果对于一个本身有序的序列，或则序列后面一大部分都是有序的序列，上面的算法就会浪费很多的时间开销，这里设置一个标志flag，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
```*/
//flag = true 代表交换过 , false代表没有交换过说明排序完成。

    public static void bubbleSort(int[] a, int n){
        assert(a);
        if(n == 1)
            return;
        int i = 0, j = 1;
        boolean flag = true; //第一次判断必须为true
        while (flag){
            flag = false;    //每次开始排序前，设置为没排序过
            for (i = 0 i < n-1; i++){//第n次排列过程
                for (j = 1; j<n-i; j++){ 
                    if (a[j-1]>a[j]){//前面的大于后面的就交换 
                        int temp = a[j-1]; 
                        a[j-1] = a[j]; 
                        a[j]=temp;
                        flag = true; //交换了就true
                    }
                }    
            }
            
        }
    }
```