交换排序--冒泡排序

冒泡排序：（low）
只会操作相邻的两个元素，每次对相邻的两个元素进行大小比较，看是否满足大小要求，一次冒泡至少会让
一个元素移动到最终位置。

例如：对一组数 4 5 6 3 2 1，进行从小到大的排序。它的第一次冒泡过程：

交换排序--冒泡排序

经过6次这样的冒泡过程，6个元素就会变成 1 2 3 4 5 6

例外：如果是 1 3 2 4 5 6 这样的序列，只需遍历一次就已经有序，所以设置一个标志位flag。

示例代码：

class SortWork {
    public static void printArray(int[] array) {//工具方法
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

public class Bubble {

    public static void main(String[] args) {
        int[] array = new int[]{2,5,4,3,7,6,1,5};
        bubbleSort(array);       
        SortWork.printArray(array);
    }

    public static void bubbleSort(int[] array) {
        int n = array.length;
        if (n <= 1) {
            return;
        } else {
            //控制冒泡的次数，一次冒泡只能确保一个元素到达最终位置
            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) {
                    System.out.println("当前遍历到第" + i + "次，数据集已经有序！");
                    break;
                }
            }
        }
    }
}

演示结果：

交换排序--冒泡排序

冒泡排序算法的执行效率：

           最好情况：
               数据集本身就是一个有序集合，O(n)

           最坏情况：
               据集完全逆序，O(n^2)

           平均复杂度：
               O(n^2)

       算法的内存消耗：
           O(1)，无需开辟新的空间，仅仅是原有的数据交换，冒泡排序是一个原地排序。

       算法的稳定性：
           冒泡排序由于相邻元素发生大小关系变换才会交换次序，所以当两个元素大小相等时，
           并不会改变其相对顺序。(稳定)

交换排序--冒泡排序

演示结果：

相关推荐