一个可视化算法与数据结构的网站
解法一、插入排序
1 问题分析并选择合适的数据结构
2 算法正确性的证明
3 算法的分析
解法一（2）、二分插入排序——插入排序的改进
解法一（3）、希尔排序——插入排序的更高效改进
解法二、冒泡排序
解法三、鸡尾酒排序——冒泡排序的改进
解法四、选择排序
解法五、归并排序
解法六、堆排序
解法七、快速排序

一个可视化算法与数据结构的网站

https://visualgo.net/en

问题定义

解法一、插入排序

1 问题分析并选择合适的数据结构

1）分析
类似于抓扑克牌：开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在手上的牌总是排序好的。

扑克

2）数据结构与伪代码
数组A[1..n]，长度A.length
原址排序输入的数

2 算法正确性的证明

1）循环不变式
在第1-8行的for循环的每次迭代开始时，子数组A[1..j-1]是由原来在A[1..j-1]中的元素组成，但已按序排列。

插入排序

2）证明
关于循环不变式，我们必须证明三条形式：
初始化：循环的第一次迭代之前，它为真
此时子数组只有一个元素A[1]，成立
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真
第4-7行找到A[j]的适当位置，第8行将A[j]插入该位置。此时的A[1..j]由原来的A[1..j]组成，但已按序拍好。
终止：在循环终止时，不变式为我们提供了一个有用的性质，该性质有助于证明算法是正确的
终止条件j > A.length，此时j = n + 1，在循环不变式中的表述中将j用n+1代替，则A[1..n]由原来的A[1..n]组成，但已排序

3 算法的分析

n = A.length
tj表示对值j地5行执行while循环测试的次数

插入排序

最好情况：已排好序

最坏情况：倒排序

插入排序的下界的另一种分析方法：

逆序：数组的一个逆序指的是数组中具有性质i < j，单A[i] > A[j]的序偶(A[i], A[j])
例如数组[34, 8, 64, 51, 32, 21]有9个逆序：
    (34, 8)  (34, 32)  (34, 21)
    (64, 51) (64, 32) (64, 21)
    (51, 32) (51, 21)
    (32, 21)

逆序的消除：通过交换相邻两个元素的顺序可以恰好消除一个逆序

由于插入算法中还有O(N)项其他工作，因此插入排序的运行时间为O(I + N)，其中I为原始数组中的逆序数。

前提：假设所有的排列都是等可能的。
定理1.N个互异数的数组的平均逆序数是N(N - 1)/4
证明：对于任意的数的表 L（5,8,9,6,4），以及其反序表 Lr（4,6,9,8,5），
它们各自的逆序数分别为：6 ((5, 4), (8, 6), (8, 4), (9, 6), (9, 4), (6, 4))，
                                          4（(6, 5), (9, 8), (9, 5), (8, 5)）。
也即表与其反序表的逆序数之和为 6+4=10，恰好是元素总数 5 关于 2 的排列数，(52)=10。

因为任意一对数（x,y）且x在前又x>y的情况（逆序数的定义）一定会在二表之一中，
所以可以说一个互异数表与其反序表的逆序数之和一定是N（N-1）/2，
也就是说任意一个互异数表的平均逆序数为 N（N-1）/4.

定理2.通过交换相邻元素进行排序的任何算法平均需要Ω(N²)
有定理1可得

这个定理告诉我们，为了使一个排序以亚二次时间运行，必须对相距较远的元素进行交换，也即每次删除应该大于1个逆序。

解法一（2）、二分插入排序——插入排序的改进

1. 问题分析及数据结构的选择

可以通过二分查找法减少比较操作的次数，快速定位要插入的位置。

伪代码：
BINARY-INSERTION-SORT(A)

for j = 2 to A.length
    key = A[j]
    left = 0, right = j - 1

    while left <= right
          mid = (left + right) / 2
          if (A[mid] > key)
                right = mid - 1
          else 
                left = mid + 1

    for i = j -1 to left
          A[j + 1] = A[j]
    A[left] = key

2. 正确性证明

本质上与插入排序是一模一样的，只不过通过了二分查找减少了比较的次数
其中二分查找法终止时：left > right，此时right = mid -1，mid = left 且有A[mid] > key
即mid是首个大于key的数，也即left是首个大于key的数，因此left的位置就是key要插入的地方

特别注意，即使是有相同元素插入的时候，left也是首个大于key位置
比如4 6 8 8 9 11，现在插入key = 8，找到的left位置还是9的位置

3. 算法分析

跟插入排序一致

解法一（3）、希尔排序——插入排序的更高效改进

1. 问题分析及数据结构的选择

伪代码：
SHELL-SORT(A)   这里的A的下标从0到A.length - 1，跟上面的插入排序略有不同
for increment = A.length/2; increment > 0; increment /=2
    for j = increment; j < A.length; ++j
        key = A[j]
        i = j - increment
        while i >= increment and A[i] > key
            A[i + increment] = A[i]
            i = i - increment
         A[i + increment] = key

2. 正确性证明

本质上是插入排序，从伪代码也可以看出

3. 算法分析

希尔排序的一个很重要的考察：

希尔排序使用一个序列h₁, h₂, ...，叫做增量序列。

hk排序的一般做法是，对于hk, hk+1, ... , N - 1中的每一个位置i，
把其上的元素放到i, i - hk, i - 2hk ... 中间的正确位置上。

这样的结果便是：一趟hk排序的作用就是对hk个独立的子数组执行一次插入排序
（子数组的元素间隔hk）

希尔排序的性能跟增量序列有关，几种常见的增量序列：
希尔增量
Hibbard增量
Knuth增量
Gonnet增量
Sedgewick增量

shell sort在适当的增量序列下快的原因在于一次消除更多的逆序对以及通过增量减少重复无意义的比较。
比如说按4排完后再按2排无疑会有一部分比较是无意义的。
因为在按4已经有序了，再按2排序能消除的逆序对就大大减少了。

定理：使用希尔排序的最坏情形 运行时间为Θ(N²)
分为两步：
1）证明下界：通过构造一个坏情形来证明
a. N是2的幂
b. 偶数位置上有N/2个最大数；奇数位置上有N/2个最小数
因此除了最后增量为1的排序外，其他排序都不会将奇数和偶数位置上的数进行排序，
那N/2个最大数仍然在偶数位置上。
原因是偶数+偶数 = 偶数（位置）；奇数+偶数=奇数（位置）

在最后一趟排序开始前第i个最小的数(i <= N/2)在位置2i-1，需要移动i-1个间隔。
      ∑i-1  (i:1~N/2) = Ω(N²)

2）证明上界：利用希尔排序的观察来证明（hk个子数组的插入排序）
带有增量hk的一趟排序有hk个关于N/hk个元素的插入排序组成，由于插入排序是二次的，
因此一趟排序总的开销是O(hk(N/hk)²) = O(N²/hk)。

对所有各趟排序求和有O(∑N²/hi  (i:1~t)) = O(N²∑1/hi  (i:1~t)，几何级数，公比为2，
几何级数的和小于2，因此总的界为O(N²)

希尔排序的下界证明例子

定理：使用Hibbard增量的希尔排序的最坏情形运行时间为Θ(N³/²)
Hibbard增量：1, 3, 7, ... , 2ⁿ - 1
1）证明下界：通过构造一个坏情形来证明
2）证明上界：
a.对于hk > N¹/²的增量，使用前面得到的界O(N²/hk)
b.对于hk<= N¹/²的增量
    需要证明的是：对于位置P上的元素Ap，当腰执行hk排序是，
    只有少数元素在位置P的左边且大于Ap

当对数组进行hk排序是，已经是hk+1和hk+2排序了。
在hk排序以前，考虑位置P和P-i上的两个元素，其中i<=P，
如果i是hk+1或者hk+2的倍数，那么显然A[P - i] < A[P]

并且，如果i可以表示为hk+1和hk+2的线性组合（非负数），那么也有A[P-i] < A[P]
举个例子：i = m * hk+1 + n * hk+2
那么有A[i] = A[P - m * hk+1 - n * hk+2 ] < A[P - n * hk+2] < A[P]

现在，hk+2 = 2 * hk+1 + 1，因此没有公因子（因为ax+by = 1，则表明两个数互质）。在这种情况下，可以证明：
至少和(hk+1 - 1)(hk+2 - 1) = 8hk² + 4hk一样大的所有整数都可以表示为hk+1和hk+2的线性组合。
因此每次while循环处理一个子数组，个数为1/hk，
而最多只有(8hk² + 4hk)/hk没有排好序 = O(hk)，
而每一趟有O(N - hk) * O(hk) = O(Nhk)

Hibbard增量序列下界的证明：（没有弄懂）

相关论文：Hibbard, Thomas N. (1963). "An Empirical Study of Minimal Storage Sorting".Communications of the ACM 6(5): 206–213.

证明：m和n互质，最大不能组合数为(m - 1)n - m

借助几个结论：
1）由于gcd(m,n)=1,所以 0,n,2*n,3*n,...(m-1)*n，对m作除，
余数肯定不同，且为{0,1,2,3...m-1}中的某数
反证法：其中若有两个对m的余数相同，
做差k2 * n - k1 * n = kn，其中 k <= m - 1
并且kn = lm，则y = kn = lm是m,n的公倍数，并且y < mn
但是由于m,n互质，其最小公倍数为mn，因此矛盾

2）设 kmin = min{ k | nk ∈ {i (mod m)} }, i ∈ [0, m)
则 nkmin 是{i (mod m)}中n的最小倍数。特别的，nm ∈ {0 (mod m)}
nkmin 是个标志，它表明{i (mod m)}中nkmin 后面所有数，
即nkmin + jm必定都能被组合出来

证明：
Lcm(m, n) = mn，所以很明显(m-1)n是最大的
因为(m-1)n是nkmin 中的最大值，
所以在剩下的m-1个剩余类中，必定有比它小并且能被m和n组合，
这些数就是(m-1)n -1，(m-1)n -2，……，(m-1)n -(m-1)
所以最大不能被组合数就是(m-1)n -m

以23, 10, 4, 1的步长序列进行希尔排序：

解法二、冒泡排序

1. 问题分析及数据结构的选择

冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2. 正确性证明

循环不变式：每次循环过后，都将前面N-1-i的元素的最大者放到N-1-i的位置上。
证明：因为两两比较时，始终将较大者放到后一个位置，因此累次比较下来，最大者就在最后面的位置上。

3. 算法分析

逆序：数组的一个逆序指的是数组中具有性质i < j，单A[i] > A[j]的序偶(A[i], A[j])
例如数组[34, 8, 64, 51, 32, 21]有9个逆序：
    (34, 8)  (34, 32)  (34, 21)
    (64, 51) (64, 32) (64, 21)
    (51, 32) (51, 21)
    (32, 21)

逆序的消除：通过交换相邻两个元素的顺序可以恰好消除一个逆序

由于插入算法中还有O(N)项其他工作，因此插入排序的运行时间为O(I + N)，其中I为原始数组中的逆序数。

前提：假设所有的排列都是等可能的。
定理1.N个互异数的数组的平均逆序数是N(N - 1)/4
证明：对于任意的数的表 L（5,8,9,6,4），以及其反序表 Lr（4,6,9,8,5），
它们各自的逆序数分别为：6 ((5, 4), (8, 6), (8, 4), (9, 6), (9, 4), (6, 4))，
                                          4（(6, 5), (9, 8), (9, 5), (8, 5)）。
也即表与其反序表的逆序数之和为 6+4=10，恰好是元素总数 5 关于 2 的排列数，(52)=10。

因为任意一对数（x,y）且x在前又x>y的情况（逆序数的定义）一定会在二表之一中，
所以可以说一个互异数表与其反序表的逆序数之和一定是N（N-1）/2，
也就是说任意一个互异数表的平均逆序数为 N（N-1）/4.

定理2.通过交换相邻元素进行排序的任何算法平均需要Ω(N²)
有定理1可得

这个定理告诉我们，为了使一个排序以亚二次时间运行，必须对相距较远的元素进行交换，也即每次删除应该大于1个逆序。

解法三、鸡尾酒排序——冒泡排序的改进

1. 问题分析及数据结构的选择

鸡尾酒排序等于是冒泡排序的轻微变形。
不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。
它可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对（由低到高），每次循环只移动一个项目。

伪代码：
cocktail_sort(A) {
    int i, left = 0, right = A.length - 1;
    int temp;
    while (left < right) {
                // 从左到右，将最大的放到最后一位
        for (i = left; i < right; i++) {
            if (A[i] > A[i + 1]) {
                swap(A[i], A[i+1])
            }
                }
        right--;
                // 从右到左，将最小的放到最前面一位
        for (i = right; i > left; i--) {
            if (A[i - 1] > A[i]) {
                swap(A[i-1], A[i])
            }
                }
        left++;
    }
}

2. 正确性证明

循环不变式：每次循环过后，都将最大的放到right位置上，将最小的放到left位置上
证明：因为两两比较时，始终将较大者放到后一个位置，因此累次比较下来，最大者就在最后面的位置上。最小同理。

3. 算法分析

同冒泡排序

解法四、选择排序

1. 问题分析及数据结构的选择

选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

伪代码：
selection_sort(A) {
    for (i = 0; i < A.length - 1; ++i) {
        min = i;
        for (j = i + 1; j < A.length; ++j) {
            if (A[j] < A[min])
                min = j;
        }
        swap(A[min], A[i])
    }
}

2. 正确性证明

正确性不言而喻，每次都是找到最小的值

3. 算法分析

逆序：数组的一个逆序指的是数组中具有性质i < j，单A[i] > A[j]的序偶(A[i], A[j])
例如数组[34, 8, 64, 51, 32, 21]有9个逆序：
    (34, 8)  (34, 32)  (34, 21)
    (64, 51) (64, 32) (64, 21)
    (51, 32) (51, 21)
    (32, 21)

逆序的消除：通过交换相邻两个元素的顺序可以恰好消除一个逆序

由于插入算法中还有O(N)项其他工作，因此插入排序的运行时间为O(I + N)，其中I为原始数组中的逆序数。

前提：假设所有的排列都是等可能的。
定理1.N个互异数的数组的平均逆序数是N(N - 1)/4
证明：对于任意的数的表 L（5,8,9,6,4），以及其反序表 Lr（4,6,9,8,5），
它们各自的逆序数分别为：6 ((5, 4), (8, 6), (8, 4), (9, 6), (9, 4), (6, 4))，
                                          4（(6, 5), (9, 8), (9, 5), (8, 5)）。
也即表与其反序表的逆序数之和为 6+4=10，恰好是元素总数 5 关于 2 的排列数，(52)=10。

因为任意一对数（x,y）且x在前又x>y的情况（逆序数的定义）一定会在二表之一中，
所以可以说一个互异数表与其反序表的逆序数之和一定是N（N-1）/2，
也就是说任意一个互异数表的平均逆序数为 N（N-1）/4.

定理2.通过交换相邻元素进行排序的任何算法平均需要Ω(N²)
有定理1可得

这个定理告诉我们，为了使一个排序以亚二次时间运行，必须对相距较远的元素进行交换，也即每次删除应该大于1个逆序。

解法五、归并排序

1 问题分析并选择合适的数据结构

将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤：
a.分解原问题为若干个子问题，这些子问题是原问题的规模较小的实例
b.解决这些子问题，递归地求解各子问题。若子问题的规模足够小，则直接求解
c.合并这些子问题的解成原问题的解

1）分析
归并排序：
a.分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列
b.解决使用归并排序递归地排序两个子序列
c.合并两个已排序的子序列以产生已排序的答案

2）数据结构与伪代码

归并算法的关键操作是“合并”。用过程MERGE(A, p, q, r)来完成合并。p <= q < r，且A[p..q], A[q+1, r]都已排好序。

2 算法正确性的证明

10-17行，通过维持以下循环不变式，执行r-p+1个基本步骤：

归并操作的正确性分析

3 算法的分析

主定理：

解法六、堆排序

1 问题分析并选择合适的数据结构

堆（优先队列）参见：http://www.jianshu.com/p/f62787325788
堆排序同样具有空间原址性：任何时候都只需要常数个额外的元素空间存储临时数据。
基本思想：利用最大堆的性质，根节点总是最大，将其不断交换到最后，然后反复构造一个新的堆（堆大小递减）

1）建堆
用自底向上的方法利用过程MAX-HEAPIFY把一个大小为n=A.length的数组A[1..n]转换为最大堆。
子数组A(floor(n/2)+1 .. n)中的元素都是树的叶节点。每个叶节点都可以看成只包含一个元素的堆。过程BUILD-MAX-HEAP对树中的其他节点都调用一次MAX-HEAPIFY。

2）维护堆的性质
最大堆的性质：除了根节点以外的所有节点i都有
A[PARENT(i)] >= A[i]
MAX-HEAPIFY，输入一个数组A和一个下标i。假定根节点为LEFT(i)和RIGHT(i)的二叉树都是最大堆，MAX-HEAPIFY通过让A[i]在最大堆中逐级下降，从而使得以下标i为根节点的子树重新遵循最大堆的性质。

step1.在i, LEFT(i), RIGHT(i)中选出最大
step2.若最大是i，则结束，否则交换，并且需要维持交换子树的最大堆性质

2 算法正确性的证明

证明BUILD-MAX-HEAP的正确性，使用如下的循环不变式：
在第2-3行中每一次for循环的开始，节点i+1, i+2, .., n都是一个最大堆的根节点。

3 算法的分析

1）建堆的分析

2）MAX-HEAPIFY的时间代价包括：调整A[i]、A[LEFT(i)]、A[RIGHT(i)]的关系的时间代价常数，加上在一棵以i的孩子为根节点的子树运行MAX-HEAPIFY的时间代价。因为每个孩子的子树的大小至多为2n/3（最坏的情况发生在最底层恰好半满的时候）

上述递归式的解为T(n) = O(lgn) = O(h)

解法七、快速排序

1 问题分析并选择合适的数据结构

与归并排序一样，快速排序也使用分治思想。对一个子数组A[p..r]进行快速排序的三步分治过程：

分解：数组A[p..r]被划分两个（可能为空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。其中，计算下标q也是划分过程的一部分
解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序
合并：因为子数组都是原址排序的，所以不需要合并操作：数组A[p..r]已经有序