JavaSE基础 - 数组排序之冒泡排序

超、凢脫俗 2022-05-28 05:09 173阅读 0赞

冒泡排序的原理：每次把最大（或最小）的那个数，通过里层的循环冒泡到末端，然后通过外层循环对剩下的数再进行一次（重复）冒泡操作。

冒泡排序的时间复杂度：冒泡排序的最好情况下时间复杂度为![b58f8c5494eef01f9d1ac17ae2fe9925bc317d07.jpg][]；最坏的情况下时间复杂度为![e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg][]。

冒泡排序的次数：N个数比较N-1遍。（未改进的情况下）

现在，我用数组元素为：89，-3，43，12，69 为例（递增排序）图解。

![20180329235517560][]

过程解释：

第一次：89大于后面的数，冒泡到最末端，得到第一次比较最大的数89.

第二次：-3 < 43,位置不变；43 > 12,交换位置；43 < 69，位置不变。得到第二次比较最大的数69.

第三，四次：可以发现，虽然第三次已经有序，但是还要走第四次。

最终得到排序数组：-3,12,43,69,89.

代码如下：

public class BubbleSort
    {
        public void sort(int[] a)
        {
            int temp = 0;
            for (int i = a.length - 1; i > 0; --i)
            {
                for (int j = 0; j < i; ++j)
                {
                    if (a[j + 1] < a[j])
                    {
                        temp = a[j];
                        a[j] = a[j + 1];
                        a[j + 1] = temp;
                    }
                }
            }
        }
    }

图解过程中，我们发现，第三次排序时，数组已经有序，但是还是要继续冒泡，无疑增加了时间复杂度，如果我们能在数组已经有序的时候就结束循环，岂不是更好.

冒泡排序的改进：改进在数组排序过程未完成，而数组已经有序列的情况下，结束循环。代码如下：

public static void bubbleSort(int[] list)
    {  
        boolean isSorted = true;	//添加有序标志。
        for (int i = 0; i < (list.length - 1) && isSorted; i++)
    	{  
            isSorted = false;  
            for (int j = 0; j < (list.length - 1 -i); j++)
    		{  
                if (list[j] > list[j + 1])
    			{  
                    int temp = list[j];  
                    list[j] = list[j + 1];  
                    list[j + 1] = temp;  
                    isSorted = true;
                }  
            }  
        }  
    }

若某次循环时，内层循环的if语句未被执行，则isSorted = false.外层循环的条件不满足，终止循环。

总结：冒泡循环是排序算法中最为基础的，掌握并理解它是必不可少的。希望我的文章对你有所帮助。

[b58f8c5494eef01f9d1ac17ae2fe9925bc317d07.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D33/sign=feddd1e257fbb2fb302b5e114e4a94f7/b58f8c5494eef01f9d1ac17ae2fe9925bc317d07.jpg
[e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D40/sign=17b28fa860d0f703e2b294dc09fa9d5c/e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg
[20180329235517560]: /images/20220528/c80ec557a49c48b593139a24f3b563a7.png