冒泡排序(Bubble Sort)

矫情吗；* 2022-07-13 09:14 211阅读 0赞

**一、冒泡排序原理**

1)临近的数字两两进行比较，按照从小到大(从大到小)的顺序进行交换，这样的一次比较过后，最大或最小的数字被交换到了最后一位
     2)然后再从头开始进行两两比较，知道倒数第二位时结束

**二、冒泡排序算法分析**

1)时间复杂度
          若文件的初始状态是正序的，一次扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin = n - 1, Mmin = 0
          所以冒泡排序最好的时间复杂度为O(n)
          若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录第三次来达到交换记录
          位置。在这种情况下，比较和移动次数均达到最大值：
          Cmax = n(n - 1)/2 = O(n2)
          Mmax = 3n(n - 1)/2 = O(n2)
          冒泡排序的最坏时间复杂度为O(n2)
          综上，因此冒泡排序总的平均时间复杂度为O(n2)
    
     2)算法稳定性
          冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素
          相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候
          也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

**三、冒泡排序示例**

例子为从小到大排序：6 2 4 1 5 9  
第一趟排序(外循环)

第一次两两比较6 > 2交换(内循环)

交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |

交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |

第二次两两比较,6 > 4交换

交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |

交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |

第三次两两比较,6 > 1交换

交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |

交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |

第四次两两比较,6 > 5交换

交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |

交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第五次两两比较,6 < 9不交换

交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |

交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第二趟排序(外循环)

第一次两两比较2 < 4不交换

交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |

交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第二次两两比较,4 > 1交换

交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |  
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第三次两两比较,4 < 5不交换

交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |  
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第四次两两比较,5 < 6不交换

交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |

交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第三趟排序(外循环)

第一次两两比较2 > 1交换

交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第二次两两比较,2 < 4不交换

交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |  
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第三次两两比较,4 < 5不交换

交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |  
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第四趟排序(外循环)无交换

第五趟排序(外循环)无交换

排序完毕,输出最终结果1 2 4 5 6 9

**四、实现代码(Java)**

public class BubbleSort {
    
        public static void main(String[] args) {
            int[] array = new int[]{
       6, 2, 4, 1, 5, 9};
            BubbleSort.bubbleSort(array);
            for(Integer i : array){
                System.out.print(i + " ");
            }
        }
    
        public static void bubbleSort(int[] array){
            int temp;//记录临时中间值
            int size = array.length;//数组大小
            for(int i = 0; i < size-1; i++){
                for(int j = i+1; j < size; j++){
       //交换两数的位置
                    if(array[i] > array[j]){
                        temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }
                }
            }
        }
    
    }

结果：1 2 4 5 6 9