冒泡排序的时间复杂度分析

1. 未优化的冒泡排序

• 内循环：因为数组下标涉及到 i+1，那么最大值为 length-2,另外每完成一次外循环，数组待处理的元素就会减少一个，因此内循环的最大值是：length -1- k

   /** * 比较次数分析： * int[] 有元素 n个 * i = 0 --> 总共有n个待处理元素 共比较n-1次 * i = 1 --> 总共有n-1个待处理元素 共比较n-2次 * i = 2 --> 总共有n-2个待处理元素 共比较n-3次 * ...... * i = n-3 --> 总共有3个待处理元素 共比较2次 * i = n-2 --> 总共有2个待处理元素 共比较1次 * * 将上面的比较次数相加得到 总比较次数： * (n-1)+(n-2)+(n-3)+ ... +3+2+1 = (1+(n-1))*(n-1)/2 = n*(n-1)/2 = (n^2 -n)/2 */
    public static void mppx(int[] oldArr){
    
        if (oldArr.length > 1){
    
            for (int k = 0; k < oldArr.length; k++) {
     // 外循环
                for (int i = 0; i < oldArr.length -1-k; i++) {
     // 内循环
                    if (oldArr[i]>oldArr[i+1]){
    
                        int max = oldArr[i];
                        oldArr[i] = oldArr[i+1];
                        oldArr[i+1] = max;
                    }
                }
            }
        }
    }

2. 优化后的冒泡排序

• 外循环优化：n个元素 实际只需要完成n-1大轮
• 如果第一次大轮（外循环）下来，如果没有发生交换，那么数组中的元素本来就是有序的，所以可以对算法进行优化

public static void mppx(int[] oldArr){
    
        if (oldArr.length > 1){
    
            int k,i,max,
                    flag=1,// 用于 本来就是有序数组的判断flag：如果第一轮外循环下来还没有发生元素交换，那就证明该数组是有序的
                    //moveCount = 0,// 记录交换次数的
                    len = oldArr.length ;
            for ( k = 0; k < len-1; k++) {
     // 外循环：循环数组中每一个元素,n个元素 实际只需要完成n-1轮
                for ( i = 0; i < len-1-k; i++) {
     // 内循环： 用于和其它元素进行比较和交换
                    if (oldArr[i] > oldArr[i+1]){
    
                        max = oldArr[i];
                        oldArr[i] = oldArr[i+1];
                        oldArr[i+1] = max;
                        flag = 0;
                        moveCount++;
                    }
                }
                // 第一大轮下来，如果没有发生交换，数组中元素就是有序的
                if (flag==1){
    
                    //System.out.println("k = " + k + "：数组中元素就是有序");
                    break;
                }
            }
            //System.out.println("moveCount = " + moveCount);
        }
    }

3. 最佳情况分析（数组中的元素本来就是有序的）

• 冒泡排序算法采用优化后（关键的flag）

数组	比较和移动次数
123	比较2次 交换0次
1234	比较3次 交换0次
12345	比较4次 交换0次
123456	比较5次 交换0次
…	…
n个有序元素	比较n-1次 交换0次

• 因此 冒泡排序的 最佳时间复杂度为： O(n)

4. 最差情况分析（数组中的元素是完全逆序的）

• 假设数组2个元素值互换的过程为一次操作

原数组 + 移动过程	比较和交换次数
21： 12	2个元素 == 比较1次 交换1次
321： 231->213->123	3个元素 == 比较(1+2)次 交换(1+2)次
4321: 3421->3241->3214->2314->2134->1234	4个元素 == 比较(1+2+3)次 交换(1+2+3)次
54321: 45321->43521->43251->43215->34215->32415->32145->23145->21345->12345	5个元素 == 比较(1+2+3+4)次 交换(1+2+3+4)次
654321：	6个元素 == 比较(1+2+3+4+5)次 交换(1+2+3+4+5)次
…	…
n个倒序元素	n个元素 == 比较(1+2+3+4+5+…+ n-1)次 交换(1+2+3+4+5+…+ n-1)次
n个倒序元素	n个元素 == 比较(n-1)*n/2次 交换(n-1)*n/2次

• 因此 冒泡排序的 最差时间复杂度是：(n-1)*n/2 + (n-1)*n/2 = n^2 -n 忽略低次幂得到 O(n^2)

5. 冒泡排序算法的稳定性

• 如果两个相邻元素相等，并不会发生交换操作，所以冒泡不会改变相同元素的下标，因此冒泡排序是一个稳定的排序算法。