排序算法之冒泡排序1

一概述

在生活中，我们离不开排序。例如在学校站队时，会按照身高顺序进行排队。每一个月考或者期末的成绩都会按照成绩排名次。

在编程学习中，我们也会经常遇到排序的问题。这种排序的场景非常多。例如在开发一个学生管理系统时，需要按照学号的顺序从小到大去排列。当开发一个电商平台时，需要把同类的商品按照价格从低到高进行排序。当开发一款游戏时，需要按照游戏得分从多到少进行排序，排名第一的玩家就是比赛的MVP。

排序看起来简单，但却蕴含着多种多样的算法和思想。那么常用的排序算法都有：

     根据时间复杂度的不同，主流的排序算法可以分为3大类：

<1>时间复杂度为O(n^2)的排序算法

冒泡排序

选择排序

插入排序

希尔排序(希尔排序比较特殊，它的性能略优于O(n^2))，但又比不上O(nlogn),所以把它归于本类。

<2>时间复杂度为O(nlogn)的排序算法

快速排序

归并排序

堆排序

<3>时间复杂度为线性的排序算法。

计数排序

桶排序

基数排序

上述都是主流的算法，在算法界里面还存在着五花八门的排序，它们都是基于传统的排序而来的，有些则是脑洞大开，如鸡尾酒排序、猴子排序、睡眠排序等。

此外排序算法还可以根据稳定性，划分为稳定排序和不稳定排序。

即就是：如果值相同的元素在排序后仍然保持着排序前的顺序，则这样的排序算法是稳定的排序；如果值相同的元素，在排序之后打乱了顺序，则这样的排序算法是不稳定的排序。例如下面的例子

在大多数的场景中，值相同的元素谁先谁后都是无所谓的。但是在某些场景中，值相同的元素必须保持原有的顺序。

二 冒泡排序

冒泡排序的英文是bubble sort，它是一种基础的交换排序。

在日常生活中，常见到的汽水，汽水中常常有许多小小的气泡哗啦啦的漂到上面去。这是因为组成小气泡的二氧化碳比水轻，所以小气泡可以一点一点的向上浮动。

而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身的大小，一点一点地向着数组地一侧移动。

具体移动的例子如下：

通过上面的图可以看出，元素9作为数列中最大的元素，就像汽水里面的小气泡一样，“漂”到最右侧。

上述就是冒泡排序的第一论。数列最右侧元素9的位置可以认为是有序的区域。有序区域目前只有一个元素。

下面是第2轮排序。

第二轮结束后，数列右侧的有序区有两个元素。

后续的交换和上述一样，就不细说了。

直至第7轮

冒泡排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都需要遍历元素，总共遍历(元素数量 - 1)轮，所以平均时间复杂度为O(n^2).

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


    }



    public static void main(String[] args) {
    int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
    sort(array);
    System.out.println(Arrays.toString(array));


    }