常见排序算法

堆排序

  1. 堆是一个数组，它可以被看成一个近似的完全二叉树，树上的每一个结点对应数组中的一个元素。除了最底层之外，该树是完全充满的，而且是从左向右填充。

  2. 二叉堆可以分为两种形式：最大堆和最小堆。最大堆中，最大堆性质是指除了根节点以外的所有结点i都要满足：A[PARENT(i)]>=A[i]，也就是说某个结点的值至多与其父结点一样大，因此堆的最大元素存放在根节点中，最小堆则相反，最小元素存放在根节点中。

  3. 堆排序算法中通常使用最大堆，最小堆通常用于构造优先队列。堆的高度为lgn，因此堆结构上的一些基本操作的运行时间至多与树的高度成正比，每个结点的操作时间复杂度为O(lgn)。因此n个结点时间复杂度为O(ngn)。

  4. 堆排序主要分为三个过程，分别是

    MAX-HEAPIFY：其时间复杂度为O(lgn)，它是维护最大堆性质的关键

    BUILD-MAX-HEAP：具有线性时间复杂度，功能是从无序的输入数据数组中构造一个最大堆

    HEAPSORT：其时间复杂度为O(nlgn)，功能是对一个数组进行原址排序（不需要额外的空间开销）

  5. 详细实现代码可见本人的github仓库

  6. 最大堆可以用来实现最大优先队列，最小堆可以用来实现最小优先队列。在建成堆的基础上对优先队列进行插入、增加元素值操作的时间复杂度为O(lgn)，得到最大值的时间复杂度为O(1)。

快速排序

  1. 快速排序最坏时间复杂度为O(n^2)，平均期望复杂度是O(nlgn)，而且其中隐含的常数因子非常小，并且能够进行原址排序不需要额外的空间开销。

常见排序算法的时间复杂度和空间复杂度

排序法 最差时间分析 平均时间复杂度 稳定性 空间复杂度
冒泡排序 O(n2) O(n2) 稳定 O(1)
选择排序 O(n2) O(n2) 不稳定 O(1)
插入排序 O(n2) O(n2) 稳定 O(1)
快速排序 O(n2) O(nlogn) 不稳定 O(nlogn)
归并排序 O(nlogn) O(nlogn) 稳定 O(1)
堆排序 O(nlogn) O(nlogn) 不稳定 O(1)
基数排序 O(logRB) O(logRB) 稳定 O(n)（B是真数(0-9)，R是基数(个十百)）
希尔排序 O(nlogn) O(ns)1<s<2 不稳定 O(1)