《数据结构与算法分析》C语言描述

目录

排序

预备知识

插入排序（$O(N^2)$）

算法

插入排序的分析

一些简单排序算法的下界

希尔排序（亚二次，但可接受的）

堆排序（$O(N\log N)$，但实践中慢于希尔）

归并排序（$O(N\log N)$）

快速排序（$O(N\log N)$，实践中最快）

选取枢纽元

分割策略

小数组

实际的快速排序例程

快速排序的分析

选择的线性期望时间算法

大型结构的排序

排序的一般下界 (用到比较的算法$\Omega(N\log N)$)

桶式排序（线性时间）

外部排序

为什么需要新的算法

外部排序模型

简单算法

多路合并

多相合并

替换选择