冒泡排序的改进

1. 加一个标志位，当某一趟冒泡排序没有元素交换时，则冒泡结束，元素已经有序，可以有效的减少冒泡次数。

   /** 
     * 引入标志位，默认为true 
     * 如果前后数据进行了交换，则为true，否则为false。如果没有数据交换，则排序完成。 
     */  
   public static int[] bubbleSort(int[] arr){  
           boolean flag = true;  
           int n = arr.length;  
           while(flag){  
               flag = false;  
               for(int j=0;j<n-1;j++){  
                   if(arr[j] >arr[j+1]){  
                       //数据交换  
                       int temp = arr[j];  
                       arr[j] = arr[j+1];  
                       arr[j+1] = temp;  
                       //设置标志位  
                       flag = true;  
                   }  
               }  
               n--;  
           }  
           return arr;  
   }
   

2. 记录每一次元素交换的位置，当元素交换的位置在第0个元素时，则排序结束。

快排优化

1. 快速排序在处理小规模数据时的表现不好，这个时候可以改用插入排序。
2. 对于一个每个元素都完全相同的一个序列来讲，快速排序也会退化到 O(n2)。要将这种情况避免到，可以这样做：

在分区的时候，将序列分为 3 堆，一堆小于中轴元素，一堆等于中轴元素，一堆大于中轴元素，下次递归调用快速排序的时候，只需对小于和大于中轴元素的两堆数据进行排序，中间等于中轴元素的一堆已经放好。