算法学习笔记 - 1 Bubble Sort

首先最基本的排序-冒泡排序

• 首先我们先了解冒泡排序的执行流程

1. 从头开始比较每一对相邻的元素,如果第1个元素大于第2个元素,则交换他们的位置 执行完第一轮后,最后一个元素就是最大的元素
2. 忽略"1"中找到的最后一个元素,重复执行1操作,直到全部元素有序

具体代码如下

protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                }
            }
        }
    }

优化1

• 如果当前的数组已经完全有序了,就可以提前终止冒泡排序,避免不必要的开销

        for (int end = array.length - 1; end > 0; end--) {
            boolean sorted = true; //用来判断是否已经有序了
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    sorted = false;
                }
            }
            if (sorted) break;//如果有序提前跳出比较
        }

优化2

• 如果数组的尾部已经局部有序,就可以记录最后一次交换的位置,减少比较次数

    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            int sortedIndex = 1;//用来记录最后一次交换位置,初始值为小于等于1的值 是为了如果已经完全有序了 end--  直接跳出排序
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }

时间空间复杂度分析 稳定性

• 最坏平均时间复杂度:O(n^2)
• 最好时间复杂度:O(n)
• 空间复杂度:O(1) 属于In-Place (原地算法)
• 稳定性:稳定