1. 概念

冒泡排序是一种简单的排序算法。只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

2.原理

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

3.针对所有的元素重复以上的步骤，除了最后一个；

4. 重复步骤1~3，直到排序完成（需要注意的每过一次外部循环，内部循环的变量需要减1，因为最大数已经到最右边了）。

3.算法分析

最佳情况：T(n) = O(n)   最差情况：T(n) = O(n2)   平均情况：T(n) = O(n2)

4.插图参考链接

https://visualgo.net/en/sorting?slide=1   
	
http://www.donghuasuanfa.com/portal
5.测试用例

 比如要排序这个数组3 2 5 4 8,带着问题去写代码，一定要手写出来！，一定要手写出来！，光看没用

public class MaoPaoSort {


    /**
     * 普通玩法就是挨个对比，需要注意点是每次对比一次后面就不用再次对比了，需要n-1
     * @param array
     * @param n
     */
    private static void bubbleSort1(int[] array,int n){
        if(n<=1){
            return;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(array[j+1]<array[j]){
                    int temp= array[j+1];
                    array[j+1]=array[j];
                    array[j]=temp;
                }
            }
        }
    }


    /**
     * 普通玩法增强版
     * @param array
     * @param n
     */
    private static void bubbleSort2(int[] array,int n){
        if(n<=1){
            return;
        }

        for(int i=0;i<n;i++){
            //循环一次没有可替换，可提前退出冒泡的标志位
            boolean flag=false;
            for(int j=0;j<n-i-1;j++){
                if(array[j+1]<array[j]){
                    int temp= array[j+1];
                    array[j+1]=array[j];
                    array[j]=temp;
                    flag=true;
                }
            }
            if(!flag){
                //没有数据交换，提前退出
                break;
            }
        }
    }


    /**
     * 增强版玩法
     * @param array
     */
    public static void bubbleSort3(int array[]){
        for(int i=0;i<array.length-1;i++){
            //有序标记，每一轮的初始值都是true
            boolean isSorted=true;
            //无序数列的边界，每次比较只需要比到这里为止
            int sortBorder=array.length-1;
            for(int j=0;j<sortBorder;j++){
                int tmp=0;
                if(array[j]>array[j+1]){
                    tmp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=tmp;
                    //因为有元素互换，所以不是有序的，标记为false
                    isSorted=false;
                    //把无须数列的边界更新为最后一次交换元素的位置
                    sortBorder=j;
                }

            }
            if(isSorted){
                break;
            }
        }

    }



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

 

排序原理

冒泡排序只会操作相邻的两个数;
	
对相邻的两个数据进行比较,看是否满足大小关系,如果不满足就互换位置;
	
一次冒泡会让至少一个元素交换到它该在的位置,重复n次就完成了排序;
	
优化:若某次冒泡不存在数据互换,就完成了n个数据的排序互换;






 

性能分析

最小时间复杂度:当数据完全有序时,只需进行一次冒泡操作,时间复杂度为O(n);
	
最大时间复杂度:当数据完全逆序时,需要n次冒泡操作,时间复杂度为O(n^2);
	
平均时间复杂度:取个中间值近似(不严谨但很实用)为n*(n-1)/4,复杂度还是O(n^2);
	
空间复杂度:每次互换只需要一个临时变量,故而空间复杂度为O(1),为原地排序算法;
	
算法稳定性:如果两个值相等,就不会交换位置,故而是稳定排序算法;

《数据结构与算法之美》 -- 王争

冒泡排序
冒泡操作只会操作相邻的俩个数据。
每次冒泡操作都会对相邻的俩个元素进行比较，看是否满足大小关系。如果不满足就让这俩个元素进行交换。
一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
eg：

可以看出：经过一次冒泡操作后，6这个元素已经在最终位置上了。要想完成所有数据的排序，只需要进行6次这样的冒泡操作。
eg：实现原始冒泡
public static void bubbleSort(int[] array) {
    if (array.length <= 1) {
        return;
    }else {
        int n = array.length;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n - i - 1;j++) {
                if (array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }
}

以上的冒泡程序是可以进行优化的。

eg：


这里的6个元素，只需要进行4次冒泡排序操作就可以了。
eg:优化冒泡排序：
public static void bubbleSort(int[] array) {  
    if (array.length <= 1) {      
        return;  
    }else {    
        int n = array.length;    
        for (int i = 0;i < n;i++) {   
            boolean flag = false;      
            for (int j = 0;j < n - i - 1;j++) {    
                if (array[j] > array[j+1]) {      
                    flag = true;                  
                    int temp = array[j];         
                    array[j] = array[j+1];       
                    array[j+1] = temp;             
                }        
            }       
            //此时没有数据交换，停止循环           
            if (!flag) {          
                break;         
            }     
        }   
    } 
}

冒泡排序算法总结：

冒泡排序是一个原地排序算法：冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为：O（1），即是一个原地排序算法。
冒泡排序是稳定的排序算法：冒泡排序中，只有交换才可以改变俩个元素的先后顺序，当相邻的俩个元素的大小相等时，即不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
冒泡排序时间复杂度分析：

最好情况下：要排序的数据已经是有序的，只需要进行一次冒泡操作，所以最好情况的时间复杂度是O（n）。

最坏情况下：要排序的数据刚好是倒序的，此时需要进行n次冒泡排序，所以最坏情况的时间复杂度是：O（n^2）。

1.冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。



 

第一，冒泡排序是原地排序算法吗？


原地排序：就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。


冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

第二，冒泡排序是稳定的排序算法吗？


稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变


在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

第三，冒泡排序的时间复杂度是多少？


时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶


最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。

 

代码实现：

    // 冒泡排序，a表示数组，n表示数组大小
    public static void bubbleSort(int[] a, int n) {
        if (n <= 1) return;
​
        for (int i = 0; i < n; ++i) {
            // 提前退出冒泡循环的标志位
            boolean flag = false;
            for (int j = 0; j < n - i - 1; ++j) {
                if (a[j] > a[j + 1]) { // 交换
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                    flag = true;  // 表示有数据交换
                }
            }
            if (!flag) break;  // 没有数据交换，提前退出
        }
    }

2.插入排序

插入排序包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。

对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。



 

 

第一，插入排序是原地排序算法吗？

从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。

第二，插入排序是稳定的排序算法吗？

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

第三，插入排序的时间复杂度是多少？

如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n)。注意，这里是从尾到头遍历已经有序的数据。

如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n2)。

还记得我们在数组中插入一个数据的平均时间复杂度是多少吗？没错，是 O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n2)。

代码实现：

    public static void insertSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int value = a[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (a[j] > value) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = value;
        }
    }

3.选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。



 

第一，选择排序是原地排序算法吗？

选择排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。

第二，选择排序是稳定的排序算法吗？

选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

我们可以从上面的动图中看到，第一次排序时，arr[0]=5，会交换到1的位置也就是arr[5]。之后的排序中，arr[2]的5最终会出现在arr[0]的前面。

第三，选择排序的时间复杂度是多少？

选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。

 

代码实现：

    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i];
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    index = j;
                }
            }
            if (index != i) {
                int tmp = arr[i];
                arr[i] = arr[index];
                arr[index] = tmp;
            }
        }
    }