【数据结构与算法】系列二十三 - 冒泡/选择/堆排序

什么叫排序（Sort）？

排序前：3,1,6,9,2,5,8,4,7

排序后：1,2,3,4,5,6,7,8,9（升序）或者 9,8,7,6,5,4,3,2,1（降序）

排序的应用无处不在，例如分数排名，价格由高到低/由低到高，身高站队等。

10大排序算法：

以上表格是基于数组进行排序的一般性结论。

冒泡、选择、插入、归并、快速、希尔、堆排序，属于比较排序（Comparison Sort）。

下面所有代码默认情况下均以升序为例子。

一、冒泡排序

冒泡排序（Bubble Sort）也叫做起泡排序。

为什么叫冒泡排序？从0开始相邻元素进行比较，一直从0位置比较到最后，就像水中的气泡往上冒一样。

1.1. 实现思路

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

public void bubbleSort(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.2. 优化一

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

第一轮扫描结束时就可以确定这个序列是否有序，因为只要没有交换变量就可以认定是有序的，所以可以通过一个变量标识是否有交换变量，如果第一轮没有交换就不需要继续扫描排序了。

public void bubbleSort(Integer[] array) {
  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]) {
        int tmp = array[begin];
        array[begin] = array[begin - 1];
        array[begin - 1] = tmp;
        sorted = false;
      }
    }
    if (sorted) break;
  }
}

但是对比优化前的代码，同样的无序数据进行排序时，优化后的代码执行效率更低（耗时更久），为什么呢？因为优化后的代码是针对有序数据的，每次循环都会额外创建sorted变量，导致内存增加，而后和sorted变量相关的代码也会无效执行。

实际开发中遇到完全有序的数据概率是很低的，所以我们需要对代码做进一步优化。

1.3. 优化二

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

按照上图，33~52的元素已经是有序的，所以不需要对这部分数据进行排序。只需要记录到索引为6的位置（即最后一次交换的位置），因为在这个位置之后的数据是不需要排序的。等下一轮循环时，截止到这个位置就停止循环，然后反复记录最后一次交换的位置（这个位置之后的数据不需要排序），直到最外层循环结束。

public void bubbleSort(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)（两个for循环全部执行），最好时间复杂度：O(n)（数据是完全有序的，只需要执行内层循环体），空间复杂度：O(1)（没有用到额外的堆空间）。

1.4. 排序算法的稳定性

如果相等的2个元素，在排序前后的相对位置保持不变，那么这是稳定（Stability）的排序算法。

排序前（3a和3b相等）：5, 1, 3a, 4, 7, 3b

稳定的排序：1, 3a, 3b, 4, 5, 7

不稳定的排序：1, 3b, 3a, 4, 5, 7

对自定义对象进行排序时，稳定性会影响最终的排序效果。

冒泡排序属于稳定的排序算法（核心代码是当左边值比右边大的时候才交换位置，如果相等不作任何处理），但稍有不慎，稳定的排序算法也能被写成不稳定的排序算法（如果相等也交换位置）。

1.5. 原地算法

什么是原地算法（In-place Algorithm）？不依赖额外的资源或者依赖少数的额外资源（空间复杂度比较低），仅依靠输出来覆盖输入。空间复杂度为O(1)的都可以认为是原地算法。

非原地算法，称为Not-in-place或者Out-of-place。

冒泡排序属于In-place。

二、选择排序

选择排序（Selection Sort）的执行流程：

为什么叫选择排序？从数组中选择一个最大的元素和末尾元素进行交换。

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

上面动画演示是找出最小的元素，和最开始的元素交换位置，不影响排序的结果。

public 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)，属于不稳定排序。

思考：选择排序是否还有优化的空间？使用堆来选择最大值（时间复杂度是logn），因为选择排序的特点就是选择最大值进行交换。

三、堆排序

堆排序（Heap Sort）可以认为是对选择排序的一种优化。

执行流程：

对序列进行原地建堆（heapify）
重复执行以下操作，直到堆的元素数量为1
- 交换堆顶元素与尾元素
- 堆的元素数量减1
- 对0位置进行1次下滤（siftDown）操作

二叉堆可回顾【数据结构与算法】系列二十 - 二叉堆】。

下面一组数据进行堆排序：

第一步，对数据进行原地建堆。

第二步，交换堆顶元素80和尾元素14，并对堆顶元素14进行下滤操作（堆数据：50、43、14、21、38）。

第三步，交换堆顶元素50和尾元素38，并对堆顶元素38进行下滤操作（堆数据：43、38、14、21）。

第四步，交换堆顶元素43和尾元素21，并对堆顶元素21进行下滤操作（堆数据：38、21、14）。

第五步，交换堆顶元素38和尾元素14，并对堆顶元素14进行下滤操作（堆数据：21、14）。

第六步，交换堆顶元素21和尾元素14，此时堆中只剩下一个元素14，排序完成。

上面示例中的第二步到第六步都是重复性的，也就是元素归位操作执行了n-1次。

复杂度分析：最好、最坏、平均时间复杂度：O(n) + O((n-1)logn) = O(nlogn)，空间复杂度：O(1)，属于不稳定排序。

public void heapSort(Integer[] array) {
  // 堆元素数量
  int heapSize = array.length;
  // 原地建堆
  for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
    siftDown(i);
  }
  
  while (heapSize > 1) {
    // 交换堆顶元素和尾部元素
    int tmp = array[0];
    array[0] = array[heapSize - 1];
    array[heapSize - 1] = tmp;

    // 交换后需要把堆元素数量减1
    heapSize--;

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

// 下滤
private void siftDown(int index) {
  int element = array[index];
  
  int half = heapSize >> 1;
  while (index < half) { // index必须是非叶子节点
    // 默认是左边跟父节点比
    int childIndex = (index << 1) + 1;
    int child = array[childIndex];
    
    int rightIndex = childIndex + 1;
    // 右子节点比左子节点大
    if (rightIndex < heapSize && array[rightIndex].compareTo(child) > 0) { 
      child = array[childIndex = rightIndex];
    }
    
    // 大于等于子节点
    if (element.compareTo(child) >= 0) break;
    
    array[index] = child;
    index = childIndex;
  }
  array[index] = element;
}