排序

排序是将表中的元素重排列为有序的过程

基于排序发生的位置可以分为:

内部排列
外部排列

其中内部排列是发生在内存中的排序算法，外部排序是发生在内存内部与内存与存储间的IO的整体排序算法。

内部排序

内部排序分为

插入排序
交换排序
选择排序
归并排序
基数排序

排序的实现基本都基于两个操作: 比较、移动

排序的稳定性

关键词存在重复时，如果排序算法可能改变关键词相对位置，则称其为不稳定的排序

插入排序

直接插入排序

插入排序遍历表，将表分为待遍历段和已插入段，将遍历后的元素向前向前遍历比较大小后插入。

通常设置 $A[0] = A[i]$ ,作为”哨兵“防止向前遍历越界

void InsertSort(ElemType A[],int n){
    int i , j;
    for (i = 2 ; i <= n ; i++){
        A[0] = A[i];
        for (j = i-1; A[0] < A[j]; --k){
            A[j+1] = A[j];
        }
        A[j+1] = A[0];
    }
}

插入排序的时间复杂度会随着表结构而改变。当目标排序表已经有序，元素只需要逐个比较，不需要移动，因此时间复杂度为 $\mathcal{O}(n)$ . 当表处于完全逆序的情况下，每一个元素都需要向前移动前方的整个表，因此时间复杂度为 $\mathcal{O}(n^2)$ .

平均情况下的时间复杂度也为 $\mathcal{O}(n^2)$

折半插入排序

折半插入排序将向前顺序查找改为了插入段的二分查找

void BInsertSort(ElemType A[],int n){
    int i,j;
    int low, mid, high;
    for(i = 2; i < n ; i++){
        A[0] = A[i];
        while(low <= high){
            mid = (low + high)/2;
            if (A[mid]>A[0]){
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        for (j = i - 1; j >= high +1; --j){
            A[j+1] = A[i];
        }
        A[high+1] = A[0];
    }
}

折半比较搜索只优化了比较过程，但是没有优化插入的过程。整体比较过程的时间复杂度为 $\mathcal{O}(n\log_2 n)$ , 总体的时间复杂度仍为 $\mathcal{O}(n^2)$

希尔排序

希尔排序将表分为等间距的子序列进行排序，再进行多次插入排序。相当于对下标模 $d_i$ 等价类内部进行排序。

希尔排序的时间复杂度也依赖于所选序列，最好的情况约为 $\mathcal{O}(n^{1.3})$ ，最坏为 $\mathcal{O}(n^2)$

希尔排序是不稳定排序

void ShellSort(ElemType A[],int n, int mod[]){
    int i,j;
    for (int r = 0; r < sizeof(mod); r++){
        int d = mod[r];
        for (i = 1; i < n-d+1 ; i++){
            for(int k = 1; k < n /3 ; K++){
                j = d * k + i;
                A
            }
        }
    }
    
}

交换排序

冒泡排序

从后往前依次比较相邻元素的关键字，逆序则交换位置。一趟排序会将最小元素浮到最前方。

void BubbleSort(ElemType A[] ,int n){
    for (int i = 0 ; i < n ; i++){
        bool flag = false;
        for (int j = n-1; j > 0 ; --j){
            if (A[j-1]>A[j]){
                int tmp = A[j-1];
                A[j-1] = A[j];
                A[j] = tmp;
                flag = true;
            }
        }
        if (flag == false){
            return ;
        }
    }
}

冒泡排序的时间复杂度:

在最好的情况下，表本来就是有序的，此时只需要遍历一遍表进行比较，时间复杂度为 $\mathcal{O}(n)$ .
在最坏的情况下，表是逆序的，总共需要

$\sum_{i}^{n-1}3(n-1) = \frac{3n(n-1)}{2} = \mathcal{O}(n^2)$

冒泡排序的相等元素不交换，因此冒泡排序是稳定排序

快速排序

快速排序的实现是基于一种类似二分的方法。

选择最左侧元素作为“枢纽”，将比枢纽小的移动到枢纽左侧，将比枢纽大的保留在枢纽右侧。枢纽的左侧右侧都形成了两个子表，两个子表再进行快速排序。

每一次移动，选定的枢纽都会被放在最终的位置上。

快速排序的最坏情况: 逆序时，每一次枢纽都需要从表的最左侧移动到表的最右侧，此时排序树是一个无分叉的树。这种情况下需要

$\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2} = \mathcal{O}(n^2)$

最好的情况是每一次都能将序列二等分，这样序列排序树是一个平衡二叉树。时间复杂度为 $\mathcal{O}(n\log_2n)$ , 是排序算法中平均性能最优的。

选择排序

简单选择排序

遍历表的第i个元素，将第i个大小的元素和第i个元素进行交换。

void SelectSort(ElemType A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            ElemType temp = A[i];
            A[i] = A[minIndex];
            A[minIndex] = temp;
        }
    }
}

简单选择排序的总比较次数和表的序无关，总需要进行 $\mathcal{O}(n^2)$ 次比较，时间复杂度始终为 $\mathcal{O}(n^2)$ , 但是在有序表时，简单选择排序移动次数为 $0$

堆排序

堆排序分为大根堆排序与小根堆排序，即满足每一个分叉结点的父亲总比两个子结点大(或者小)的完全 $n$ 叉树。

二叉堆的构建

首先通过BFS遍历表构建一个完全二叉树，再自底而上的调整表的结构，将小元素上浮，上调从下向上，从右向左，和二叉树的顺序表存储方式的逆向方向相同。

二叉堆的删除

输出堆顶元素后删除该元素，同时将堆底元素(完全二叉树的最后一个元素)移动到根结点。然后自上而下的调整子树。

二叉堆的性能

二叉堆的构建的时间复杂度为 $\mathcal{O}(n)$ , 每一次的堆调整的时间复杂度为 $\mathcal{O}(\log_2n)$ , 因此总时间复杂度为
$\mathcal{O}(n\log_2 n)$

2路归并排序

表的每一个元素视为归并的有序段进行两两归并。归并段之间不一定是有序的，通过两个头指针进行比较，类似拉链式的进行合并。

归并操作需要额外的一倍空间存储归并段，因此空间复杂度为 $\mathcal{O}(n)$ 。归并是二分的，归并次数是完全二叉树的深度 $\lceil\log_2 n\rceil$ , 因此时间复杂度为 $\mathcal{O}(n\log_2 n)$

归并排序是外部排序的基石，外部排序是基于k路排序展开的

基数排序

基数排序是对于元素 $r$ -进展开后对每一个系数进行比较，使用链表管理。

假设表内的元素可以表示为

$a = \sum_{i = 1}^n k_i r^i$

第一次比较按 $k_1$ 的大小顺序排列，按表中的顺序用链表串联 $k_1$ 中相等的元素，再相连形成一个整链表。再按照 $k_2$ 的顺序串联，以此类推遍历 $k_i$ ，最后实现排序。

外部排序

外部排序旨在提升内存、外存的排序以及内外存IO开销性能。依照发展逻辑递进分为四个模块：

多路归并 -- 内存排序的优化
败者树 -- 归并段的归并方式的优化
置换-选择排序 -- 生成初始归并段的优化
最佳归并树 -- 整体归并的策略最优化

多路归并排序

这个部分和内部排序的归并排序是一致的。

对于 $r$ 个归并段的 $k$ 路归并，完全 $k$ 叉树的归并趟数为 $S = \lceil \log_k r\rceil$

败者树

基于多路归并排序的外部排序的总比较次数为

$S(n-1)(k-1)=\lceil\log_k r\rceil(n-1)(k-1)$

这随着 $k$ 递增，因此内部归并效率会随着归并路数增加而降低。

如何优化多路归并，使归并过程是 $k$ 无关的呢？如果是 $k$ 无关的，理论上我们就可以无限提高归并路数以提高效率。对数化的消元总是基于平衡树的。

败者树类似于小根堆，将归并段的小元素一个个压入一个段。基于归并段构建一个完全二叉树，每一个父结点进行两个子结点的比较，将更大的元素的归并段序号存储，将更小的归并段的序号推入祖先结点。

败者树的比较次数为 $\lceil\log_2k\rceil$ , 因此总比较次数优化为了

$S(n-1)\lceil\log_2k\rceil = \lceil\log_2r\rceil(n-1)$

Tip: 受限于缓冲区， $k$ 并不是越大越好，会增大外存的读写开销。

置换-选择排序

置换-选择排序应用于归并段的初始构建。对于相等的数据量，越长的归并段意味着归并段的数量越少，则归并 $k$ 叉树也越矮。

置换-选择算法设置了一个容量为 $w$ 的工作区。将待排文件的前 $w$ 个元素压入工作区后输出比输出文件段所有元素更大的最小元素(称为MINIMAX)，然后再输入待排文件的第一个元素，压入MINIMAX。当工作区的元素都不符合MINIMAX时，输出文件作为归并段输出，进行下一轮归并段的构建。

工作区选择最小元素的方式是败者树，对于工作区的数据对象是小一级的归并段而不是单个元素对象时，败者树可以实现多头输入与输出升序序列。

最佳归并树

最佳归并树是基于Huffman 树实现整体的归并策略I/O次数最小的方式，即如何构建归并 $k$ 叉树，能使得归并的次数最少。

最佳归并树的每一个结点权是外存归并段内的对象个数，每一次执行归并都需要进行权重的内外存I/O，因此这个 $k$ 叉树的最小 $\text{WPL}$ 即为最优I/O访问次数。

Huffman树总认为可以是数据结点加补0结点构成的正则 $k$ 叉树，因此满足

$\begin{cases} n=n_k+n_l\\ n=kn_k+1 \end{cases}$

即

$n_l\equiv 1\quad(\mathrm{mod} \,k-1)$

因此补0的个数为 $k-u-1$ 个，即可生成完整的归并树

算法数据结构

排序