冒泡排序

问题：

设有一数组，其大小为10个元素（int str[10]）数组内的数据是无序。现在要求我们通过编程将这个无序的数组变成一个从小到大排序的数组（从下标为0开始）

选择排序思路：

按照题目的要求，毫无疑问，正确的结果应该就像这样： 1 2 3 4 5 6 7 8 9 10 要做到这样，最简单和最直接想到的方法就是进行对比交换。
<li>首先，把10个数里最小的个数放到下标为0的位置上（str[0]）
<li>通过将下标为0的数（str[0]）与剩下其余9个数进行对比交换（将较少者放置在下标为0的位置上），就可以得到这10个数最小的那个。
<li>10个数最小的那位确定后，接下来就要找剩下9个数最小的那个。
<li>因为已经确定出一个最小的数，所以就不要动str[0]，直接从str[1]开始，与剩下的8个数对比交换，找出9个数中最小的那位放到下标为1（str[1]）的位置上。
<li>继续按照这个思路就可以将这十个数变成有序的（从小到大）的数组。

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] sortArray = new int[1000];
        for(int i = 0; i < 1000; i++){
            sortArray[i] = (int) (Math.random()*1000);
        }
        selectSort(sortArray);
        print(sortArray);
    }

    private static void print(int[] sortArray) {
        
        for(int i = 0; i < sortArray.length; i++){
            System.out.print(i == sortArray.length - 1 ? sortArray[i] : (sortArray[i]+" , "));
        }
    }

    private static void selectSort(int[] sortArray) {
        for(int i = 0; i < sortArray.length;i++){
            for(int j = i+1 ; j < sortArray.length;j++){
                if(sortArray[i] > sortArray[j]){
                    swap(sortArray,i,j);
                }
            }
        }
    
    }
    private static void bubbleSort(int[] array){
        for(int i = 0; i < array.length;i++){
            for(int j = array.length - 1 ; j > i;j--){
                if(array[j] < array[j - 1]){
                    swap(array,j,j - 1);
                }
            }
        }
        
    }
private static void betterBubbleSort(int[] array){
        boolean flag = true;
        for(int i = 0; i < array.length && flag;i++){
            flag = false;
            for(int j = array.length - 1 ; j > i;j--){
                if(array[j] < array[j - 1]){
                    flag = true;
                    swap(array,j,j - 1);
                }
            }
        }
    }
    private static void swap(int[] array,int i, int j) {
        array[i] = array[i]^array[j];
        array[j] = array[j]^array[i];
        array[i] = array[i]^array[j];
    }
    
}

这个方法是比较容易想到的实现方法。但存在不足：就是本来位于前面的较小数被交换到后面。

那么怎样解决这个不足呢？

可以使用冒泡排序。

什么是冒泡排序呢？

你可以这样理解：（从小到大排序）存在10个不同大小的气泡，由底至上地把较少的气泡逐步地向上升，这样经过遍历一次后，最小的气泡就会被上升到顶（下标为0），然后再从底至上地这样升，循环直至十个气泡大小有序。 在冒泡排序中，最重要的思想是两两比较，将两者较少的升上去 冒泡排序最坏情况的时间复杂度是O(n²)

private static void bubbleSort(int[] array){
        for(int i = 0; i < array.length;i++){
            for(int j = array.length - 1 ; j > i;j--){
                if(array[j] < array[j - 1]){
                    swap(array,j,j - 1);
                }
            }
        }
    }

冒泡排序算法只会将较少的逐步向上推，不会造成文章前面所说的不足，这里就不给予演示。

有些追求完美的人就会思考，冒泡排序能不能优化呢？

答案是可以的。

那么如何优化?

通过观察可以看到，造成没必要的操作主要原因是后面8个数的顺序都已经是有序。所以，我们可以通过设置一个标记变量，标记数列中的数是否在循环结束前就已经排好序。

private static void betterBubbleSort(int[] array){
        boolean flag = true;
        for(int i = 0; i < array.length && flag;i++){
            flag = false;
            for(int j = array.length - 1 ; j > i;j--){
                if(array[j] < array[j - 1]){
                    flag = true;
                    swap(array,j,j - 1);
                }
            }
        }
    }

根据优化过的代码，当最好情况的时候，冒泡排序的时间复杂度是O(n)。