数据结构与算法（第二季）：冒泡、选择、堆排序

冒泡排序（Bubble Sort）

一、概念

• 从头开始比较每一对相邻元素，如果第一个比第二个大，就交换它们的位置。
• 执行完一轮后，最末尾那个元素就是最大元素。
• 忽略上一步中曾经找到的最大元素，重复执行步骤一，直到全部元素有序。

二、代码实现

static void bubbleSort1(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        for (int begin = 1; begin <= end; begin++) {
            if (array[begin] < array[begin - 1]) {
                int tmp = array[begin];
                array[begin] = array[begin - 1];
                array[begin - 1] = tmp;
            }
        }
    }
}
复制代码

三、代码优化

1、 第一种优化

• 如果序列已经完全有序，可以提前终止冒泡排序。

image

• 增加一个bool值，用于判断一次循环后是否有数据交换，如果没有，则退出排序。
• 如果数据不是完全有序，此优化会因添加成员变量而导致计算时间更长。

static void bubbleSort2(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        boolean sorted = false; //是否进行过排序
        for (int begin = 1; begin <= end; begin++) {
            if (array[begin] < array[begin - 1]) {
                int tmp = array[begin];
                array[begin] = array[begin - 1];
                array[begin - 1] = tmp;
                sorted = true; // 此轮循环进行过排序
            }
        }
        if (!sorted) break;
    }
}
复制代码

2、 第二种优化

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

image

• 记录上一次循环最后一次交换的位置，将其作为下一次循环的截止位置。

static void bubbleSort3(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        // sortedIndex的初始值在数组完全有序的时候有用
        int sortedIndex = 1;
        for (int begin = 1; begin <= end; begin++) {
            if (array[begin] < array[begin - 1]) {
                int tmp = array[begin];
                array[begin] = array[begin - 1];
                array[begin - 1] = tmp;
                sortedIndex = begin;
            }
        }
        end = sortedIndex;
    }
}
复制代码

• 平均时间复杂度O(n^2)
• 最好时间复杂度O(n)
• 空间复杂度O(1)

四、排序算法的稳定性（Stability）

• 如果相等的2个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法。
  • 排序前：5，1，3a，4，7，3b
  • 稳定的排序：1，3a，3b，4，5，7
  • 不稳定的排序：1，3b，3a，4，5，7
• 冒泡排序是稳定排序算法。

五、原地算法（In-place Algorithm）

• 不依赖额外的资源或依赖少数的额外资源，仅依靠输出来覆盖输入。
• 空间复杂度为O(1)的都可以认为是原地算法。
• 非原地算法，称为Not-in-place或者Out-of-place。
• 冒泡排序属于In-place。

选择排序（Selection Sort）

一、概念

• 从序列中找出最大的那个元素，然后与最末尾的元素交换位置。执行完一轮后，最末尾的那个元素就是最大的元素。
• 忽略上一步中曾经找到的最大元素，重复执行上一步。

二、代码实现

static void selectionSort(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        int maxIndex = 0;
        for (int begin = 1; begin <= end; begin++) {
            if (array[maxIndex] <= array[begin]) {
                maxIndex = begin;
            }
        }
        int tmp = array[maxIndex];
        array[maxIndex] = array[end];
        array[end] = tmp;
    }
}
复制代码

• 选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序。
• 最好，最坏，平均时间复杂度：O(n^2)，空间复杂度：O(1)。
• 属于不稳定排序。

堆排序（Heap Sort）

一、概念

• 堆排序可以认为是对选择排序的一种优化。

• 执行步骤：

  1. 对序列进行原地建堆。

image

1. 交换堆顶与尾元素。 2. 堆的元素数量减1。 3. 对0位置进行1此siftDown操作。

image

• 重复执行1-3操作，直到堆的元素数量为1。

  image

• 最好，最坏，平均时间复杂度：O(nlogn)。

• 空间复杂度O(1)，属于不稳定排序。

二、代码实现

public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    private int heapSize;

    @Override
    protected void sort() {
        // 原地建堆
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }

        while (heapSize > 1) {
            // 交换堆顶元素和尾部元素
            swap(0, --heapSize);

            // 对0位置进行siftDown（恢复堆的性质）
            siftDown(0);
        }
    }

    private void siftDown(int index) {
        T element = array[index];

        int half = heapSize >> 1;
        while (index < half) { // index必须是非叶子节点
            // 默认是左边跟父节点比
            int childIndex = (index << 1) + 1;
            T child = array[childIndex];

            int rightIndex = childIndex + 1;
            // 右子节点比左子节点大
            if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0) { 
                child = array[childIndex = rightIndex];
            }

            // 大于等于子节点
            if (cmp(element, child) >= 0) break;

            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }
}