gevent源码目录结构:

File Meaning
AUTHORS 作者列表
CHANGES.rst 各个版本的历史修改记录
CONTRIBUTING.rst 为gevent作贡献的方式
LICENSE 许可
MANIFEST.in 文件清单
Makefile Makefile,包含编译及测试等自动化命令
NOTICE 注意,一些特殊内容的不同许可
README.rst 简介,github主页
TODO TODO, iss tracker
_setupares.py c-ares的setup脚本
_setuplibev.py libev的setup脚本
_setuputils.py psutil的setup脚本
appveyor/ windows平台的持续化集成
appveyor.yml appveyor的配置
benchmarks/ 性能测试脚本
deps/ 依赖的第三方包(c-ares, libev)
dev-requirements.txt 开发安装依赖
doc/ 文档
examples/ 应用实例
rtd-requirements.txt rtd安装依赖
scripts/ 一些脚本
setup.cfg setup配置
setup.py* setup脚本
src/ gevent源码
tox.ini 持续集成配置
util/ 一些应用脚本

堆排序

堆排序利用了堆的特性进行排序。堆是一种近似完全二叉树的结构,满足以下性质:子节点的键值总是小于(或大于)它的父节点。

堆排序的C实现:

void sink(int *n, int i, int len)
{
    int l = 2*i + 1;
    if (l > len - 1) return;
    int r = l + 1;
    int _max_lr = (r > len - 1) ? l : (*(n+r) > *(n+l) ? r : l);
    if (*(n+_max_lr) < *(n+i)) return;
    swap(n+_max_lr, n+i);
    sink(n, _max_lr, len);
}

void heap(int *n, int len)
{
    int i;
    for (i=(len-1)/2; i>=0; i--) {
        sink(n, i, len);
    }

    print_n_array(n, 10);
    for (i=0; i<len; i++) {
        swap(n, n+len-1-i);
        sink(n, 0, len-i-1);
    }
}

堆排序最差情况的时间复杂度为\(n \lg n\) .堆排序需要的额外空间为\(O(1)\) .堆排序是不稳定的.

堆排序与快排的比较

  • 快排总体来说较堆排序更快
  • 快排最差情况下接近\(O(n^2)\)
  • 快排需要更多的额外空间

因此,考虑到堆排序最差情况的复杂度上限和需要额外空间的上限,通常将其应用在对实时性要求较高和安全性较高的嵌入式系统中。

堆排序与归并排序的比较

  • 二者时间复杂度均为\(n \lg n\) .
  • 堆排序在数据缓存较小的计算机上更快,因为堆排序需要更少的额外空间。
  • 堆排序不稳定,归并排序稳定。
  • more

归并排序

归并排序是把两个或两个以上有序列表合并为一个新的有序列表。

归并排序的C实现(递归版本):

void merge(int *n, int len)
{
    if (len <= 1) return;

    int half = len / 2;
    merge(n, half);
    merge(n+half, len-half);

    int *_n = (int *) malloc(half * sizeof(int));
    memcpy(_n, n, half * sizeof(int));

    int i=0, j=half, k=0;
    while (i<half && j<len) {
        *(n+ k++) = *(n+j) < *(_n+i) ? *(n+ j++) : *(_n+ i++);
    }
    while (i<half) {
        *(n+ k++) = *(_n+ i++);
    }
            free(_n);
}

复杂度计算:

\begin{equation*} \left\{ \begin{array}{l} T(1) = 1 \\ T(n) = 2 T(\frac n 2) + n \end{array} \right. \end{equation*}

解之可得:

\begin{equation*} T(n) = n \log_2 n \end{equation*}

比较操作的次数介于\((n \log n)/2\)\(n \log n - n + 1\) 之间。赋值操作的次数是\(2n \log n\) 。归并算法的空间复杂度为:\(O(n)\) .

归并排序是唯一的稳定的复杂度为\(O(n \log n)\) 的排序算法。

MORE