1.冒泡排序定义:

冒泡排序是最简单最容易理解的排序算法之一，其思想是通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。

 

2.普通版:

/**     * 一般排序     */    private void bubbleSort0() {        int[] is             ={95,85,12,52,64,74,105,502,4,7,6,1,74,60,141,19,34,45,59};        Log.i(TAG, "开始--"+ Arrays.toString(is));        int handleCount=0;        int swapCount=0;        for (int i=0;i
     
      is[j+1]){                    swap(is,j,j+1);                    swapCount++;                }                handleCount++;            }        }        Log.i(TAG, "bubbleSort0: --handleCount:"+handleCount+",swapCount:"+swapCount+"\r\n"+ Arrays.toString(is));    }
     

2.1:输出结果:

 

 3.优化版:

　　冒泡排序过程中，可以检测到整个序列是否已经排序完成，进而可以避免掉后续的循环

 3.1代码:

/**     * 在非最坏的情况下，冒泡排序过程中，可以检测到整个序列是否已经排序完成，进而可以避免掉后续的循环：     */    private void bubbleSort1() {        int[] is             ={95,85,12,52,64,74,105,502,4,7,6,1,74,60,141,19,34,45,59};        Log.i(TAG, "开始--"+ Arrays.toString(is));        int handleCount=0;        int swapCount=0;        for (int i=0;i
     
      is[j+1]){                    swap(is,j,j+1);                    swapCount++;                    isSwap=true;                }                handleCount++;            }            if (!isSwap){                break;//已经没有交换了,跳出循环            }        }        Log.i(TAG, "bubbleSort1: --handleCount:"+handleCount+",swapCount:"+swapCount+"\r\n"+ Arrays.toString(is));    }
     

 3.2输出结果:

 

 4.再次优化版: 

　　在每轮循环之后，可以确认，最后一次发生交换的位置之后的元素，都是已经排好序的，因此可以不再比较那个位置之后的元素

4.1代码:

/**     * 进一步地，在每轮循环之后，可以确认，最后一次发生交换的位置之后的元素，都是已经排好序的，因此可以不再比较那个位置之后的元素，大幅度减少了比较的次数：     */    private void bubbleSort2() {        int[] is             ={95,85,12,52,64,74,105,502,4,7,6,1,74,60,141,19,34,45,59};        Log.i(TAG, "开始--"+ Arrays.toString(is));        int handleCount=0;        int swapCount=0;        int n=is.length-1;        for (int i=0;i
     
      is[j+1]){                    swap(is,j,j+1);                    swapCount++;                    newN=j+1;                }                handleCount++;            }            n=newN;            if (n==0){
    //位置没有变化说明已经交换好了,跳出循环                break;            }        }        Log.i(TAG, "bubbleSort2: --handleCount:"+handleCount+",swapCount:"+swapCount+"\r\n"+ Arrays.toString(is));    }
     

 4.2输出结果:

 

5.进一步优化: 

　　进行双向的循环，正向循环把最大元素移动到末尾，逆向循环把最小元素移动到最前

5.1代码:

/**     *进行双向的循环，正向循环把最大元素移动到末尾，逆向循环把最小元素移动到最前     */    private void bubbleSort3() {        int[] is             ={95,85,12,52,64,74,105,502,4,7,6,1,74,60,141,19,34,45,59};        Log.i(TAG, "开始--"+ Arrays.toString(is));        int handleCount=0;        int swapCount=0;        int endPoint=is.length-1;        int startPoint=0;        while (startPoint<=endPoint){            int newEndPoint=startPoint;            int newStartPoint=endPoint;            for (int j=startPoint;j
     
      is[j+1]){                    swap(is,j,j+1);                    swapCount++;                    newEndPoint=j+1;                }                handleCount++;            }            endPoint=newEndPoint-1;//这里一个元素已经沉底了,所以下一次交换次数相比于最后一次交换要少1            for (int j=endPoint;j>startPoint;j--){                if (is[j]
     

 5.2输出结果: