详解Java八大经典内排序算法——冒泡排序

      今天我们走近第二个大类【交换排序】中的冒泡排序

      通过无序区中相邻元素间关键字的比较和位置的交换，使关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”。整个算法是从最下面的元素开始，对每两个相邻的关键字进行比较，且使关键字较小的元素换至关键字较大的元素之上，使得经过一趟冒泡排序后，关键字最小的元素到达最上端。接着，再在剩下的元素中找关键字次小的元素，并把它交换到第二个位置上。依次类推，一直到所有元素都有序为止。

▲ 冒泡排序的一趟排序过程

※说明：冒泡排序每趟产生的有序区一定是全局有序区，也就是说每趟产生的有序区中所有元素都归位了。

      设待排序的表有 10 个元素，其关键字为 {9,8,7,6,5,4,3,2,1,0}。以下为冒泡排序的排序过程：

      每次从无序区中冒出一个关键字最小的元素（用方框表示）并将其定位。

▲ 冒泡排序过程

    时间复杂度：O(n²)；

    空间复杂度：O(1)；

    稳定性：稳定；

    复杂性：简单。

      在有些情况下，在第 i （i < n-1）趟时就已经排好序了，但算法仍执行后面几趟的比较。实际上，一旦算法中某一趟比较时没有出现任何元素交换，说明已排好序了，就可以结束本算法。为此，改进冒泡排序算法如下：

      今天就分享到这里啦~

     下次我们继续分享【交换排序】中的另一位成员快速排序，记得关注呦~