如何来评价一个排序算法的好坏？
有下面三个方面:
- 时间复杂度: 最好情况，最坏情况，平均时间复杂度(怎么优化时间开销？ 一种方式是使用更高效的算法，另一种方式是缩短内部循环的次数.)
- 空间复杂度，是否会消耗额外的内存空间, 是否是原地排序？
- 稳定性，我们可能会对同一组元素按照不同的关键字进行多次排序，如果待排序的序列中存在值相同的元素，那么经过排序后，相等元素之间原来的顺序是否变化？
这几种算法的原理是差不多的:
- 将待排序数组分为已排序和未排序两部分
- 每次排序，将未排序部分的某个元素移动到已排序部分指定的位置
- 重复N次
所以，它们都是『两层循环』，外层循环控制轮数，内层循环把元素移动到指定的位置。
对于冒泡来说，它的内层循环做的事情，就是比较相邻元素的值，然后把较大的值放到右边，这样一轮下来，最大的值就在右边，然后放到已排序数组的末尾, 重复N次，那么整个数组就有序了.
void sort_bubble(ItemType a[], int l, int r){
int i, j, changed;
for (i = l ; i < r; i++) {
for (j = r, changed = 0; j > i; j--) {
if (less(a[j], a[j-1])) {
exch(a[j], a[j-1]);
changed = 1;
}
}
if (!changed) break;
}
}
- 最好：o(n)，比如 待排序数组 1,2,3,4,5，循环一次
- 最坏 o(n^2),比如 待排序数组 5，4，3，2，1
- 平均 o(n^2)
- 属于原地排序,O(1)
- 属于稳定排序
插入排序，它的内层循环做的事情，就是把未排序部分的元素依次插入到有序部分的指定位置去。这样外层循环每一轮下来，未排序部分的长度减一，直到未排序部分全部排序完，整个数组就有序了。
void sort(ItemType a[], int l, int r){
int i, j;
for (i = l + 1; i <= r; i++) {
for (j = i; j>l; j--) {
compexch(a[j-1], a[j]);
}
}
}
/*
插入排序
sort实现中有几个可以优化的点：
1. 当我们碰到的键不大于正在被插入的键时，应该停止compexch操作.
2. j > l 测试通常是多余的，我们通过提前把数组的最小值放在第0个位置，可以避免测试语句的调用.
3. compexch实现里面，交换指令需要三条指令，我们可以采用数据移动方案来减少指令的数量
*/
void sort_insert(ItemType a[], int l, int r){
int i, j, min = l, v;
for (i = l+1; i <= r; i++) {
if (less(a[i], a[min])) min = i;
}
//数组a的第一个元素为最小元素, 避免内层循环的判断
exch(a[min], a[l]);
for (i = l + 2; i <= r ; i++) {
v = a[i];
for (j = i; less(v, a[j-1]); j--) {
a[j] = a[j-1];//如果v比前一个元素小，向后移动一位
}
a[j] = v;
}
}
插入1：sort
排序随机元素time: 0.000069 s
排序已排序的数据源time: 0.000056 s
排序逆序的数据源time: 0.000109 s
插入优化后: insertion
排序随机元素time: 0.000005 s
排序已排序的数据源time: 0.000004 s
排序逆序的数据源time: 0.000004 s
- 最好: O(n),比如 待排序数组 1,2,3,4,5，循环一次
- 最坏:O(n^2),比如 5，4，3，2，1
- 平均:O(n^2)
- 运行的实际和输入数据有关, 如果输入数据中逆序对很少时，那么插入排序是很高效的算法. 数据移动的次数等于逆序对个数.
- 插入排序对于部分有序的数组非常高效，也很适合小规模数组.
- 属于原地排序，O(1)
- 属于稳定排序
选择排序，它的内层循环做的事情，就是在未排序部分找到最小的元素，然后放在有序部分的末尾，这样N轮下来，未排序部分的长度每次减一，最后整个数组就有序了。
void sort_select(ItemType a[], int l, int r){
int i, j, min;
for (i = l; i <= r; i++) {
min = i;
for (j = i+1; j <= r; j++) {
if (less(a[j], a[min]))
min = j;
}
exch(a[min], a[i]);
}
}
- 最好,最坏，平均都是O(n^2),因为每次都会在未排序部分迭代找最小项, 排序一个已经排好顺序的数组，逆序的数组或随机的数组所花的时间是一样的.
- 属于原地排序,O(1)
- 非稳定，比如5,8,5,2,9。第一轮下来，2和5交换，那么这两个5的顺序就发生变化了.
- 内部循环目的是为了查找当前未排序数组的最小项，然后在外层循环更新到已排序数组的末尾，所以它的交换次数为N-1，对于一些具有庞大项，小键指的文件，使用选择排序更为合适，因为数据移动的次数会非常少.
这三种算法，选择排序是最戳的，它的交换(N-1)和比较次数(N^2 / 2)是固定的, 跟输入数据无关. 冒泡和插入相当，但是插入性能会比冒泡更好，因为冒泡里面核心步骤是交换，而插入排序核心步骤是移位和赋值，它的指令会更少些.
插入排序的性能与数据中的「逆序对」有关。要统计文件中的「逆序对」，我们可以对每个元素左边比它大的元素的数目进行累加来计算。在插入排序中，这个累加的数目就是元素要在插入时要向前移动的步数，如果「逆序对」为0，那么插入排序无需数据移动，整个执行时间是线性的. 对于另外一种部分有序的数组，可能是对已排好序的数组添加一些新元素等使用插入排序就会非常高效，而选用冒泡和选择排序效率就不高.
前面的O(n^2)的算法适合小规模的数据排序，当涉及到大规模数据的排序问题，归并和快爬就用的上了.
归并和快排都用到了分治思想，非常巧妙。
归并排序的思想：如果要排序一个数组，我们先将数组从中间分为两部分，然后分别对两部分排序，最后再将排序好的两部分合并在一起。
void _merge(ItemType a[], ItemType aux[], int l, int mid, int r);
void _sort_merge(ItemType a[], ItemType aux[], int l, int r);
void sort_merge(ItemType a[], int l, int r){
int sz = r - l + 1;
//利用辅助数组，避免频繁创建数组带来的消耗
ItemType aux[sz];
_sort_merge(a, aux, l, r);
}
void _sort_merge(ItemType a[], ItemType aux[], int l, int r){
if (l >= r) return;
int mid = l + (r - l)/2;
//先将左右两半分别排序，然后将结果合并起来
_sort_merge(a, aux, l, mid);
_sort_merge(a, aux, mid+1, r);
_merge(a, aux, l, mid, r);
}
void _merge(ItemType a[], ItemType aux[], int l, int mid, int r){
int i = l, j = mid+1, k;
for (k=l; k<=r; k++) {
aux[k] = a[k];
}
//原地排序
for (k=l; k<=r; k++) {
if (i > mid) {
a[k] = aux[j++];
}else if (j > r){
a[k] = aux[i++];
}else if (less(aux[i], aux[j])) {
a[k] = aux[i++];
}else{
a[k] = aux[j++];
}
}
}
为了减少频繁创建temp数组的消耗，我们使用aux数组作为辅助数组，每次排序之前先将数组内容复制到它里面，然后在原数组里面进行原地排序.
以上归并排序属于自顶向下的归并排序，除此之外还有自底向上的归并排序，它的思想在于：我们先递归的合并小数组，然后在成对的合并大数组。
void sort_merge_bottom2up(ItemType a[], int l, int r){
int sz, i, N = r - l + 1;
ItemType aux[N];
for (sz = 1; sz < N; sz+=sz) {
for (i = l; i < N - sz; i+=sz+sz) {
_merge(a, aux, i, i+sz-1, MIN(i+sz-1+sz, N - 1));
}
}
}
_merge 方法保持不变，我们先两两合并，然后四四合并.... 最终即获得排序数组. 需要注意的是最后一个子数组的大小并非一定等于sz大小，当数组大小为偶数情况下，才会等于sz大小，所以需要注意下标越界的处理.
自底向上的归并排序非常适合链表的归并排序，只需要重新组织链接就能将链表进行原地排序.
性能分析:
- 运行的实际和输入数据无关，时间复杂度为N * lgN
- 稳定排序
- 需要额外O(N)的内存消耗， 非本地排序
对于大规模数组问题，归并排序比插入排序快很多，N * lgN级别的算法只比顺序变量数组多了常数倍的时间. 而N^2级别的算法就相当慢了，这里有一个对比分析:
// 数据规模
#define N 100000
插入排序：
排序随机元素time: 8.752243 s
排序已排序的数据源time: 0.000522 s
排序逆序的数据源time: 17.232562 s
归并排序：
排序随机元素time: 0.024600 s
排序已排序的数据源time: 0.015237 s
排序逆序的数据源time: 0.015296 s
对于小规模数组排序，或者数组有序度特别高的排序任务，插入排序的性能更高，它近乎O(N)级别, 而归并排序因为会有频繁的函数调用开销，所以说插入排序更适合:
// 数据规模
#define N 15
插入排序:
排序随机元素time: 0.000002 s
排序已排序的数据源time: 0.000003 s
排序逆序的数据源time: 0.000001 s
归并排序:
排序随机元素time: 0.000005 s
排序已排序的数据源time: 0.000004 s
排序逆序的数据源time: 0.000002 s
快速排序是最广泛的排序算法之一，它流行的原理在于实现简单，并且适用于各种不同的输入数据，排序所用的时间是N * lgN级别，还是原地排序.
快速排序的思想在于：通过分治的思想，利用切分函数，将数组分为三部分，左数组的值都不大于切分值，右数组的值都不小于切分值，然后递归的对左数组和右数组进行排序。待左数组和右数组完成排序之后，那么由左数组，切分值，右数组组成的数组也一定是有序的.
int partition(ItemType a[], int l, int r);
void sort_quick(ItemType a[], int l, int r){
if (l >= r) return;
int idx = partition(a, l, r);
sort_quick(a, l, idx-1);
sort_quick(a, idx+1, r);
}
int partition(ItemType a[], int l, int r){
int t = a[l], i = l, j = r+1;
while (1) {
//从左边开始寻找第一个比t大的值
for (; less(a[++i], t); )
if (i == r) break;
//从右边开始寻找第一个比t小的值
for (; less(t, a[--j]); )
if (j == l) break;
if (i>=j) break;
exch(a[i], a[j]);
}
exch(a[l], a[j]);
return j;
}
排序随机元素time: 0.010274 s
排序已排序的数据源time: 12.567573 s
排序逆序的数据源time: 11.469472 s
快速排序的性能最终依赖切分函数的效果，而这依赖于切分值的选择，例如利用上面的程序来排序一个已有序的数组，第一次选择最小的元素来切分，第二次选择次小的元素来切分，如此这般，每次调用划分出来的「左数组」都只有一个元素，这意味着算法性能掉回了O(N^2). 我们需要改进这些情况， 可以使用三数选中法来避免:
void _setMid(ItemType a[], int l, int r){
int min, mid = l + (r - l) / 2;
if (less(a[l], a[r])){
min = less(a[mid], a[r]) ? mid : r;
}else{
min = less(a[mid], a[l]) ? mid : l;
}
exch(a[r], a[min]);
}
int _partition(ItemType a[], int l, int r){
_setMid(a, l, r);
int t = a[r], i = l, j = l;//i代表比t小的数组的末尾
for (; j < r; j++) {
if (less(a[j], t)) {
exch(a[j], a[i]);
i++;
}
}
exch(a[i], a[r]);
return i;
}
- 大部分情况下都能做到O(n*log(n))
- 最坏情况下，O(n^2)，比如数组本身就是有序的，它将会进行N次分区(可以使用三数取中避免)
- 原地排序,O(1)
- 非稳定排序
这三种排序的是O(n)级别的排序算法，不过它们对排序数据的要求极其严格，之所以能做到线性的时间复杂度，主要原因是，这三种算法是非基于比较的算法，都不涉及元素间的比较。
这三种算法对排序数据要求很严苛，重点在与理解这些排序算法适用的场景.
桶排序的核心思想是：将要排序的数据分到几个有序的桶里，每个桶再单独排序，最后根据桶的顺序依次取出，组成的序列就有序的。这里对数据的要求有几方面:
- 待排序数据要很容易就能分进M个桶里
- 并且这桶和桶之间天然的就是有序的
- 每个桶里面的元素要劲量平均，不然算法就会退化大O。
计数排序是一种特殊情况下的桶排序，在这里每个桶的划分力度为1个单位，所以每个桶内部是不需要重新排序的。很容易理解.
计数排序适合用在数据范围不大的场景中，如果数据范围比要排序的数据n大很多的话，那么就不适合计数排序了。
使用索引排序或指针排序的主要原因是避免侵扰被排序的数据，甚至当被排序的数组是只读时，我们任然能够进行排序。 并且如果我们想要对待排序数组进行多个维度的排序也是非常方便的，通过不修改原始数据，而是建立多个索引数组来进行排序。
使用索引排序或指针排序的第二个原因在于可以避免移动整个记录的开销.
当需要将原数组按照已排好序的索引数组进行排序时，一种常规的方法是:
for (i=0; i< N; i++)
datasorted[i] = data[a[i]];
但这需要额外足够的内存来存储数组的另一个拷贝，同时我们也不能盲目的设置data[i] = data[a[i]]来实现原地排序，因为这会覆盖掉data[i]的旧值，导致旧值丢失.
就位排序算法就是用来解决这个问题来的
void insitu(ItemType data[], int a[], int n){
int i,j,k;
for (i=0; i<n; i++) {
ItemType v = data[i];
j = i;
while (a[j] != i) {
data[j] = data[a[j]];
k = a[j]; //k保存下一个即将遍历的位置下标
a[j] = j; //标记当前数据已经搬移到正确位置
j = k;
}
data[j] = v;
a[j] = k;
}
}
ItemType data[] = {'A', 'S', 'O', 'R', 'T', 'I', 'N', 'G', 'E', 'X','A','M','P', 'L', 'E'};
//索引数组的意义在于数组的最小元素下标为0, 数组的次小元素下标为10.....
int idxs[] = {0, 10,8,14,7,5,13,11,6,2,12,3,1,4,9};
insitu(data, idxs, 15);
print(data, 15);
如果a[j] == i，那么表示任何元素已经就位了，否则，将data[j]的值保存到v里面，然后通过循环a[j],a[a[j]]....依次处理，直到再次到达索引i为止.
支持两种操作:
- 删除最大元素
- 插入元素
应用场景比如：任务调度，新加入的任务总是有优先级的，而我们需要首先执行那些优先级更高的任务.
初级实现里面，插入和删除最大元素这两个操作之一在最坏情况下需要线性时间来完成，比如基于数组的实现, insert就像压栈一样无需任何额外操作，而delMax则需要O(N)遍历找出来，然后和队首元素交换后删除. 或者insert干脆就维护成一个有序的数组，最大元素位于队首，那么delMax只需O(1)即可完成. 我们需要寻求一种更高性能的实现方式.
这种方式就是「基于数组实现的二叉堆」， 在堆的世界里，每个节点的值都比它的两个子节点的值要大，同时这条规则也是递归定义的， 所以堆首元素就是最大/最小元素.
堆的两个操作，插入和删除最大元素都会打破堆维持的平衡状态，所以，每次插入或删除最大元素后，我们都需要执行某些操作，来继续维持堆的平衡:
当向堆的末尾插入新的元素，有可能这个值比它的父节点的值还要打，所以需要不断的上浮，直到找到它的父节点的值比它大的位置.(这就好像新手刚进职场，然后打怪升级一步一步爬到管理层)
//上浮操作，将制定元素上浮到它应该在的位置
static void swim(maxpq *m, int i){
while (i > 1 && maxpq_less(m, i/2, i)) {
exch(m->a[i/2], m->a[i]);
i /= 2;
}
}
删除堆的最大元素，首先先将堆首元素和堆末尾元素交换，交换之后，最大值就位于队尾，我们只需要移动堆顶指针即可，但是新的堆首元素可能又会比它的子节点小，所以需要不断的下沉.
//下沉操作，将制定元素下沉到它应该在的位置
static void sink(maxpq *m, int i){
while (2 * i <= m->n) {
int j = 2 * i;
if (j+1 <= m->n && maxpq_less(m, j, j+1)) {
j++;
}
if (maxpq_less(m, i, j)) {
//swap
exch(m->a[i], m->a[j]);
i = j;
}else break;
}
}
插入和删除的代码如下:
void maxpq_insert(maxpq* m, ItemType v){
m->a[++m->n] = v;
swim(m, m->n);
}
ItemType maxpq_delmax(maxpq* m) {
ItemType maxv = maxpq_max(m);
exch(m->a[1], m->a[m->n]);
m->n--;
sink(m, 1);
return maxv;
}
性能分析:
基于数组的二叉堆是一个完全二叉树结构，树的高度为lg(N), 上浮要做的是把堆尾的元素上浮到堆首去，下沉做的是把堆首的元素下沉到堆尾去，所以它们的时间复杂度为lg(N)级别.
堆排序的是将优先队列变成一种排序方法, 该排序方法有两个阶段:
第一个阶段是将原始数据重新组织成一个堆，例如如果我们想正序排序，那么我们创建一个大顶堆。
创建大顶堆的过程我们是从右到左调用sink函数(sink函数时从当前节点触发，有可能它的值比它的子节点小，所以一直下沉到最终的位置)构建子堆，它的核心理念在于「如果一个节点的左右节点都已经是堆结构，那么在该节点调用sink后可以将它们变成一个堆，这时的最大元素就在队首」， 递归这个过程，直到我们在位置1上调用sink，扫描结束.
构建堆的过程目的是劲量将大元素放到数组的前面，最大元素在队首，次大元素在它的附近. 这样我们获取最大元素将非常效率.
for (k = n / 2; k >= 1; k--) {
sink(a, n, k, cmp);
}
第二阶段依次将堆首的最大元素放到数组末尾，并将堆的大小缩短，直到堆被处理完成，这个有点像选择排序，每次将最大元素放到数组的末尾，但是它的比较次数是非常少的.
for (k = n-1; k>1; ) {
exch(a[1], a[k]);
k--;
sink(a, k, 1, cmp);
}
完整代码如下:
//构建初始堆
int k, n;
n = r - l + 1;
for (k = n / 2; k >= 1; k--) {
sink(a, n, k, cmp);
}
//依次将堆首的最大元素放到数组末尾，并将堆的大小缩短，直到堆被缩短完成
for (k = n-1; k>1; ) {
exch(a[1], a[k]);
k--;
sink(a, k, 1, cmp);
}