Sort Algorithm

prologue

　　这是算法导论系列的第一篇文章。该系列主要将记录自己在学习算法导论的过程中的一些笔记以及心得体会等。接下来的几个月内应该会陆陆续续地更新，可能打算做比较多期，希望能够继续坚持做下去吧。在这个系列中，代码方面将以类似于算法导论中的伪代码的形式记录(或者是C语言)，另外，该系列文章均假设读者对基础的数据结构有一定的了解(链表，栈，队列等)。
　　今天的第一期主题就是排序算法，作为应用最广泛的算法之一，排序算法在整个算法体系中有着举足轻重的作用。因此，现在就让我们一起来学习吧。下文排序均默认按照从小到大的顺序。

normal sort algorithm

　　以下几种算法是最基础的排序算法，思路较为简单，实现起来比较容易，但是复杂度均为$$O(n^2)$$
　　当然，常数比较小，在小数据的情形下和其他算法花费的时间还是比较接近的。

bubble sort

　　提到排序算法，我们最容易想到的也许就是冒泡排序了。如同它的名字一样，冒泡排序的做法就是用“冒泡”的形式不断将较小的数字提升到前面来。我们可以通过以下的排序方式实现:

void bubbleSort(int* a, int len) {
    for (int i = 0; i < len; i++) {
        bool flag = false;
        for (int j = len-1; j > i; j--) {
            if (a[j] < a[j-1]) {
                swap(a[j],a[j-1]);
                flag = true;
            }
        }
        if (!flag) break;
    }
}

　　思路很简单，我们也很容易能够看出，冒泡排序的复杂度是O(x^2)，然而，冒泡排序存在几个问题：

有时候数组已经有序了，但是冒泡排序还是会继续进行循环，导致效率降低，上面我们采用了一个标记，当数组已经有序时，循环退出
当数组是逆序存储时，冒泡排序需要进行很多次的交换，导致效率降低，事实上我们会发现，一个数字从底部冒泡一次一格移动到顶部是很浪费时间的，因此就有了一种优化的办法：双向冒泡排序，这种优化算法能一定程度上降低常数

　　另外，冒泡排序还有一个很重要的作用就是，它可以用来计算逆序对(j>i 但是 a[j]<a[i])的个数，注意到当我们交换两个数字时，整个数组的逆序对的数量就减少了1，因此我们只要统计数组的交换次数，就可以计算总逆序对的数量了。

insert sort

　　插入排序也是一种很经典的排序算法。具体就是一开始建立一个空数组，每次我们往其中插入一个数字，并维护数组的有序性，最后得到的就是一个有序的数组了。具体做法如下:

void insertSort(int* a, int len) {
    for (int i = 1; i < len; i++) {
        for (int j = i; j > 0; j--) {
            if (a[j] < a[j-1]) swap(a+j,a+j-1);
            else break;
        }
    }
}

select sort

　　选择排序同样是一种简单的排序算法，和插入排序类似，选择排序同样是逐步往数组中插入元素，但不同的是选择排序每次选择最大的那一个数字插入数组中，最后得到一个有序的数组，具体做法如下:

void selectSort(int* a, int len) {
    for (int i = 0; i < len; i++) {
        int idx = i, _min = a[i];
        for (int j = i+1; j < len; j++) {
            if (a[j] < _min) {
                _min = a[j];
                idx = j;
            }
        }
        swap(a[i],a[idx]);
    }
}

improved sort algorithm

　　前面我们用到的集中算法都有着一个很大的问题：复杂度太高了，这样的复杂度对我们来说很难接受。人们发明了很多其他优秀的算法来进行排序，使得时间复杂度降低到O(nlogn)。以下就是几种最经典的优化算法。

heap sort

　　按照算法导论的顺序，第一个讲到的应该是堆排序。这种排序用到了二叉堆，其中，二叉堆支持以下操作：

INSERT 把元素插入堆中，保证维护堆的特性，复杂度为O(logn)
REMOVE 移除堆顶元素，具体做法是将该元素交换到堆的尾部，然后重新调整堆即可。复杂度O(logn)

　　有了这样的一个堆的结构，我们就可以逐步往数组中插入所有元素，然后再一个一个弹出，最后按照弹出的顺序，我们得到了一个有序的数组(这里数组的下标从1开始)。
　　具体的代码如下:

#define LSON(a) ((a)<<1)
#define RSON(b) ((b)<<1|1)
// 这里只是为了方便而设置为全局变量，最恰当的做法应该是把这些函数封装为一个结构体
int heapSize = 10;
void maxHeapify(int* a, int i) {
    int l = LSON(i);
    int r = RSON(i);
    int largest = i;
    if (l <= heapSize && a[l] > a[largest]) {
        largest = l;
    }
    if (r <= heapSize && a[r] > a[largest]) {
        largest = r;
    }
    if (largest != i) {
        swap(a+largest, a+i);
        maxHeapify(a, largest);
    }
}
void buildHeap(int* a) {
    for (int i = heapSize/2; i > 0; i--) {
        maxHeapify(a, i);
    }
}
void heapSort(int* a) {
    buildHeap(a);
    for (int i = heapSize; i > 1; i--) {
        swap(a+i,a+1);
        heapSize--;
        maxHeapify(a, 1);
    }
}

　　我们会发现，堆排序的时间复杂度还是十分不错的，建树和排序的复杂度均为O(nlogn)，最后总体的复杂度还是O(nlogn)。比起前面的几种算法，这是一个很大的优化。另外，堆排序还能应用于实现优先队列。堆中的每个节点存放的是关键字以及一些卫星数据。我们依照关键字实现一个最大堆或者最小堆，每次需要的时候就直接弹出即可。

merge sort

　　和堆排序类似，归并排序也是一种十分优秀的排序算法，不过归并没有用到堆这样的一种数据结构，而是用到了分治的思想，同样是一种应用广泛的算法思想。
　　分治，即分而治之。对与一个长度为N的数组的排序问题，我们可以试着将这个问题规模变小。我们知道，一个问题规模越小，往往越有助于我们的求解。因此，我们不妨考虑下将一个这个数组分成两个大小为N/2的数组，如果我们拥有两个长度为N/2的有序数组，那么我们可以在O(n)的时间内将这两个数组合并为一个长为N的数组。依次递归下去，直到数组的长度变为O(1)，退出递归。这样，我们就得到了这个表达式：
$$T(n)=2*T(n/2)+O(n)$$
　　使用代入法或主方法，我们可以得到这个表达式的解为T(n)=O(nlogn)。
　　具体代码如下:

#define N 100
int c[N];
void merge(int*a, int l, int r) {
    int mid = (l+r)>>1, p1 = l, p2 = mid+1;
    for (int i = l; i <= r; i++) {
        // 每次获取两个子数组的队头中更大的那一个加入数组c
        if (p1 > mid) {
            c[i] = a[p2];
            p2++;
        }
        else if (p2 > r) {
            c[i] = a[p1];
            p1++;
        } else {
            if (a[p1] < a[p2]) {
                c[i] = a[p1];
                p1++;
            } else {
                c[i] = a[p2];
                p2++;
            }
        }
    }
    for (int i = l; i <= r; i++) {
        a[i] = c[i];
    }
}
void mergeSort(int*a, int l, int r) {
    if (l >= r) return;
    int mid = (l+r)>>1;
    mergeSort(a, l, mid);
    mergeSort(a, mid+1, r);
    merge(a,l,r);
}

quick sort

　　快速排序，对于刚刚了解排序的人来说是一个比较难的算法。其解决问题的思路并不是那么直接。因此，需要我们多花点时间在这上面。尽管快速排序在最坏情况下的复杂度达到了Θ(n^2)，但是期望复杂度却是Θ(nlogn)。更重要的是，它隐含的常数因子是很小的，在大多数情况下，其表现比堆排序，归并排序还要优秀一些。
　　和归并排序类似，快排也用到了分治的思想，但是其做法和归并差别很大。对于归并排序来说，我们选择的是将数组平均分成两个部分，通过将这两个部分分别排序后再进行合并，我们成功地把复杂度降低到了O(nlogn)。然而，快排的思路是从数组中选出一个数字，并且按照比该数字小或比该数字大，将数组分成了两个部分，并依次对这两个部分进行递归。最后我们就得到了一个有序的数组了。由于每一次递归我们都能保证左边任何数字都小于右边的任何数字，我们最终能保证得到的数组是有序的。
　　算法具体如下:

int partition(int* a, int l, int r) {
    int key = a[r];
    int i = l-1;
    for (int j = l; j < r; j++) {
        if (a[j] <= key) {
            i++;
            swap(a+j,a+i);
        }
    }
    i++;
    swap(a+i,a+r);
    return i;
}
void quickSort(int* a, int l, int r) {
    if (l < r) {
        int mid = partition(a, l, r);
        quickSort(a, l, mid-1);
        quickSort(a, mid+1, r);
    }
}

　　在最理想的情况下，我们的数组被key平均地分成了两个部分，我们得到递归式$$T(n)=2*T(n/2)+Θ(n)$$
　　看起来我们的快排似乎没什么问题了，复杂度是Θ(nlogn)。但是，如果我们仔细观察快排选取key的策略的话，我们会发现，当遇到一个数组本来就有序时，每个步骤中数组被划分为了长度为0和N-1的两个部分，快排的复杂度竟然高达了Θ(n^2)，这对我们来说是不能接受的。那么平均情况呢？我们假设快排产生一次最佳划分和一次最差划分，则两次划分后，我们还是得到了两个长度近似为N/2的数组，这说明了我们的快速排序还是十分优秀的。另外，可以证明，即使快排产生的划分十分不均匀时(比如1:9)，我们得到的时间复杂度依然为O(nlogn)，可以使用递归树证明。
　　为了解决快排出现最坏情况的问题，我们可以采用一种随机的方式对快排进行简单的优化，每一次我们选取的不再是最右边的点，而是一个随机的位置，这样就能在很大程度上避免快排达到Θ(n^2)复杂度的情况了。我们只需更改quickSort函数即可。

void quickSort(int* a, int l, int r) {
    if (l < r) {
        int x = rand()%(r-l+1)+l;
        swap(a[x],a[r]);
        int mid = partition(a, l, r);
        quickSort(a, l, mid-1);
        quickSort(a, mid+1, r);
    }
}

　　接下来，我们考虑如何证明快速排序的期望复杂度为Θ(nlogn)。为了证明这个问题，我们考虑Partition函数中的for语句。显然，算法最多调用n次partition函数，那么我们如果能求出partition中，if语句的期望执行次数X，那么我们就可以得到快排的复杂度为Θ(n+X)
　　如何计算比较操作的执行次数呢？这里需要扩充一下定义，我们将数组A的元素重新命名为$z_i$，表示数组A中第i小的元素，并且还定义了Z表示一个区间:$Z_{ij} = {z_i, z_{i+1}, …, z_j}$
　　另外，我们还要用到算法导论第五章讲到的指示器随机变量:
$$X_{ij}=I\,\{z_i与z_j比较\}$$
　　由此，我们得到了算法的总比较次数，再由数学期望的线性特性，我们可以得到:
$$X = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{ij}$$
$$
E(X)=E[\,\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{ij}\,]
= \sum_{i=1}^{n-1}\sum_{j=i+1}^n E[\,X_{ij}\,]
= \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}Pr\{z_i与z_j进行个比较\}
$$
　　那么，$z_i和z_j比较$的概率究竟怎么算？从正面比较难考虑的话我们可以试着从反面考虑:两个元素不会进行比较的情况。考虑快速排序的一个输入为1-10这10个数字(顺序任意)，并假设第一个主元为7，那么数字被分为两个集合{1,2,3,4,5,6}和{8,9,10}，并且第一个集合任意元素不会再和第二个集合的任意元素有比较了。这就告诉我们，在元素互异的情况下，一旦一个满足$z_i < x < z_j$的主元x被选择后，$z_i,z_j$就不会再有比较了。而在这个区间上，这每一个数字被选到的概率应该是相等的。由此，我们得到:
$$
\begin{align}
Pr\{z_i与z_j比较\} =& Pr\{z_i或z_j被选为Z_{ij}的第一个主元\}\\
=& Pr\{z_i是Z_{ij}的第一个主元\}+Pr\{z_j是Z_{ij}的第一个主元\}\\
=& \frac{1}{j-i+1}+\frac{1}{j-i+1}\\
=& \frac{2}{j-i+1}
\end{align}
$$
　　再将两个式子联立，我们可以得到:
$$
\begin{align}
E[X] =& \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1} \\
=& \sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac{2}{k+1}\\
=& \sum_{i=1}^{n-1}\sum_{k=1}^{n}\frac{2}{k}\\
=& \sum_{i=1}^{n=1}O(logn)\\
=& \,O(nlogn)
\end{align}
$$
　　最终，在元素互异的前提下，我们得到了快速排序期望复杂度的一个上界O(nlogn)
　　另外，书中还给出了另外一种证明快排的复杂度的方法，这种方法关注的不是比较的次数，而是每一次单独递归调用的期望运行时间。利用递归式和不等式放缩，最后再使用代入法进行证明，这里省略了。
　　这样就结束了吗？当然不是。我们其实还会发现一个问题，如果元素不互异呢？假如现在有一个数组，其中所有元素都相同，这个时候复杂度是多少呢？结果有点遗憾，是O(n^2)。为了处理这样的一种情形，我们可以采取这样的一种措施，在partition函数中，将原数组分为3个部分，左边部分比key小，右边部分比key大，中间部分和key的大小相同，这样就解决了这个问题了。
　　此外，在具体进行快速排序的时候，还有一个小优化可以做:当数组长度很小时(比如n<8)，我们可以转换排序策略，选择插入排序。测试表明，插入排序在数组很小的时候复杂度是比较优的。经过这样的调整，能在某种程度上提高快排的运行效率。

other sort algorithm

　　前面我们提到的两类排序算法复杂度分别为O(n^2)和O(nlogn)。这些排序算法都有一个相同的特点——各元素的次序依赖于对他们的比较，这类排序被称为比较排序。为了解决排序算法的下界问题，我们需要用到决策树模型。决策树是一颗完全二叉树，它可以表示在给定输入规模的情况下，某一特定排序算法对所有元素的比较操作。树中每个内部节点以i:j标记。每个叶子节点对应一个数列。排序算法的执行则相当于一条从树的根节点到叶节点的路径。到达一个叶节点时，表明排序已经完成。
tree
　　对于一个n个元素的数组，共有n!种排列，每一种排列都必须位于树的某一个节点。若设该决策树有l个节点，高度为h，则我们有:
$$n! <= l <= 2^h$$
　　对两边取对数，我们有:
$$
\begin{align}
h &>= lg(n!)\\
&= Ω(nlgn)
\end{align}
$$
　　由此，我们得到了比较排序算法的一个下界为Ω(nlgn)。那么我们如果想要突破这个下界，就不能采用比较的关系去实现排序算法了。我们需要另辟溪径。
　　桶排就是这样的一个算法，它平均情况下的复杂度为O(n)，看起来要比前面的所有算法都要优秀许多。
　　桶排假设数服从均匀分布。假设数据分布在区间[0,1)上，现在给n个桶，那么我们将区间分为n个相同大小的子区间，并对应于给定的桶，将位于区间内的数放到对应的桶中，最后遍历每个桶，并对桶中的每个数字进行排序，再按顺序列出即可。当然，也可以使用Hash，将某些区间的值映射到某个桶中。
　　另外，还有计数排序和基数排序，他们都是运行时间十分优秀的算法，不过需要使用额外的空间，且依赖于数字的大小，但在某些情况下能够有较优异的表现。

epilogue

　　到这里，我们的算法导论系列的第一期就结束了。这一期主要记录了一些排序算法的思想，重点关注快排，归并这两种算法。我们简单地提了这些排序算法的写法，并提了一下复杂度的分析。接下来，按照算法导论的顺序，下一期可能要写一下红黑树的笔记吧。