Sorting¶

概述

Insertion Sort 插入排序
Shellsort 希尔排序
Heapsort 堆排序
Mergesort 归并排序
Quicksort 快速排序
Indirect sort 间接排序
Bucket Sort 桶排序
Radix Sort 基数排序
Topological Sorting 拓扑排序
选择排序
冒泡排序

Preliminary¶

void X_sort(ElementType A[],int N)

N 为合法整数（一般为正整数）
假设数组元素均为整数
基于比较的排序（comparison-based sorting）（<, >, = 有定义）
仅考虑内部排序（internal sorting）
稳定排序（stable sorting）：如果两个元素相等，在排序后它们的相对位置不变

外部排序 -- 数据量大于内存的情况，通常使用归并排序

Selection & Bubble

Selection Sort 选择排序：

对于一个长度为 \(n\) 的数组，每一趟从未排序的部分选择最小（或最大）元素，然后放到已排序部分的末尾（或开头）,重复 \(n‑1\) 次

升序

void selection_sort(int arr[], int n){
    int i, j, min_idx;

    for(i = 0; i < n - 1; i++){
        min_idx = i;

        for(j = i + 1; j < n - 1; j++){
            if(arr[j] < arr[min_idx]){
                min_idx = j;
            }
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}

Bubble Sort 冒泡排序：

void bubble_sort(int arr[], int n){
    int i, j, temp;

    for(P = n - 1; P > 0; P--){
        int flag = 0;

        for(j = 0; j < P; j++){
            if(arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
                flag = 1;
        }
        if(!flag) break;
    }
}

顺序：\(T=O(n)\) 逆序：\(T=O(n^2)\)

稳定
数组链表均可

Insertion Sort¶

插入排序
从 P = 1 到 P = N - 1 重复 N - 1 次排序（0 ~ P-1 有序），对于第 P 次排序，将位置 P 上的元素向前 P 个元素移动，直到发现正确的位置插入。

类比扑克牌

code

Insertion Sort

void insertion_sort(ElementType A[], int N){
    int P, i;
    ElementType temp;

    for(P = 1; P < N; P++){
        temp = A[P]; // 摸下一张牌

        for(i = P; i > 0 && A[i - 1] > temp; i--){
            A[i] = A[i - 1]; // 移出空位
        }
        A[i] = temp; // 插入新牌
    }
}

顺序：\(T=O(n)\) 逆序：\(T=O(n^2)\)

稳定

A Lower Bound for Simple Sorting Algorithms

时间复杂度下界
逆序对（inversion）：对于一个数组，如果存在 \(i < j\) 且 \(A[i] > A[j]\)，则称 \((i, j)\) 是一个逆序对

对于冒泡/插入排序：交换2个相邻元素正好消去1个逆序对

插入排序：\(T(N,I) = O(N + I)\)，其中 \(I\) 是原始数组中逆序对的数量

定理 1: 任意N个不同元素组成的序列平均具有 \(N(N-1)/4\) 个逆序对
定理 2: 任何仅以交换相邻元素为基本操作的排序算法的平均时间复杂度为 \(\Omega(N^2)\)

Shellsort¶

希尔排序

缩小增量排序（diminishing increment sort） - 不稳定

增量序列（increment sequence）
\(h_k\)-sort
- \(h_k\)-sort
希尔增量序列（Shell's increment sequence）
- \(h_k = \lfloor \frac{N}{2^k} \rfloor\)，直到 \(h_k = 1\)

code

    void  shellsort(ElementType A[], int N){
        int 
    }

希巴德增量序列（Hibbard's increment sequence）

\(h_k = 2^k - 1\)，直到 \(h_k \geq N\)
比希尔增量序列更快
不稳定

补充

塞奇威克增量序列（Sedgewick's increment sequence）

\(h_k = 4^k + 3*2^{k-1} + 1\)，直到 \(h_k \geq N\)
比希尔增量序列更快
不稳定

Knuth's increment sequence

\(h_k = 3^k - 1 / 2\)，直到 \(h_k \geq N\)
比希尔增量序列更快
不稳定

Tokuda's increment sequence

\(h_k = \lceil \frac{9^k - 4^k}{5*4^{k-1}} \rceil\)，直到 \(h_k \geq N\)
比希尔增量序列更快
不稳定

Heapsort¶

堆排序
堆（heap）：完全二叉树，满足堆序性质
堆序性质：对于最大堆，父节点的值大于等于子节点的值；对于最小堆，父节点的值小于等于子节点的值
堆的实现：使用数组表示完全二叉树，父节点索引为 \(i\) 的子节点索引为 \(2i + 1\) 和 \(2i + 2\)，父节点索引为 \(i\) 的父节点索引为 \(\lfloor \frac{i - 1}{2} \rfloor\)
堆排序算法：
1. 构建最大堆
2. 将堆顶元素与堆的最后一个元素交换，减少堆的大小，重新调整堆
3. 重复步骤 2 直到堆的大小为 1

Mergesort¶

归并排序
分治法（divide and conquer）
稳定
外部排序（external sorting）：适用于数据量大于内存的情况
归并（merge）：将两个有序数组合并成一个有序数组
归并排序算法：
1. 将数组分成两半，递归地对每一半进行归并排序
2. 将两半合并成一个有序数组
3. 重复步骤 1 和 2 直到数组大小为 1
4. 时间复杂度为 \(O(n \log n)\)，空间复杂度为 \(O(n)\)
5. 适用于链表排序，因为链表的插入和删除操作效率较高

Quicksort¶

快速排序
分治法（divide and conquer）
不稳定
快速排序算法：
1. 选择一个基准元素（pivot）
2. 将数组分成两部分，左边的元素小于基准元素，右边的元素大于基准元素
3. 递归地对左边和右边的部分进行快速排序
4. 时间复杂度为 \(O(n \log n)\)，空间复杂度为 \(O(\log n)\)（平均情况），最坏情况为 \(O(n)\)（当数组已经有序或逆序时）
5. 适用于数组排序，因为数组的随机访问效率较高

Indirect sort¶

间接排序
稳定
间接排序算法：
1. 创建一个索引数组，存储原数组元素的索引
2. 对索引数组进行排序，比较原数组元素的值
3. 根据排序后的索引数组重新排列原数组
4. 时间复杂度为 \(O(n \log n)\)，空间复杂度为 \(O(n)\)
5. 适用于需要保持原数组不变的情况，或者需要根据某些属性进行排序的情况

表排序（table sort）

表排序：一种特殊的间接排序，适用于需要根据多个属性进行排序的情况，例如按照姓名、年龄、成绩等多个属性进行排序
通过创建一个包含多个属性的索引数组，可以实现多属性排序

Bucket Sort¶

桶排序
非比较排序（non-comparison sort）
稳定
桶排序算法：
1. 将输入数据分到有限数量的桶中，每个桶内的数据范围相同
2. 对每个桶内的数据进行排序，可以使用其他排序算法
3. 将所有桶内的数据合并成一个有序数组
4. 时间复杂度为 \(O(n + k)\)，空间复杂度为 \(O(n + k)\)，其中 \(k\) 是桶的数量
5. 适用于输入数据均匀分布在一个范围内的情况

Radix Sort¶

基数排序
非比较排序（non-comparison sort）
稳定
基数排序算法：
1. 将输入数据按照位数进行分组，从最低位开始排序
2. 对每个位数进行排序，可以使用计数排序（counting sort）作为子程序
3. 重复步骤 1 和 2 直到最高位排序完成
4. 时间复杂度为 \(O(d(n + k))\)，空间复杂度为 \(O(n + k)\)，其中 \(d\) 是数字的位数，\(k\) 是每个位数的取值范围
5. 适用于整数排序，或者字符串排序（按字符位数进行排序）的情况

Topological Sorting¶

拓扑排序
有向无环图（DAG）：一种特殊的有向图，包含有向边但不包含有向环
拓扑排序算法：
1. 计算图中每个顶点的入度
2. 将所有入度为 0 的顶点加入一个队列
3. 当队列不为空时，执行以下操作：
  - 从队列中取出一个顶点，将其加入拓扑排序的结果
  - 对该顶点的所有邻接点进行处理，将它们的入度减 1
  - 如果某个邻接点的入度变为 0，将其加入队列
4. 如果拓扑排序的结果包含所有顶点，则排序成功；否则，图中存在有向环，无法进行拓扑排序
5. 时间复杂度为 \(O(V + E)\)，空间复杂度为 \(O(V)\)，其中 \(V\) 是顶点的数量，\(E\) 是边的数量
6. 适用于任务调度、编译器优化等需要处理依赖关系的情况

HW11 -- Insertion Sort¶

HW12 -- Shellsort & Mergesort¶

HW13 -- Heapsort & Quicksort¶