排序¶
插入排序¶
void insertionSort(int arr[], int n) {
for (int P = 1; P < n; ++P) {
int tmp = arr[P];
int i;
for (i = P; i > 0 && arr[i - 1] > tmp; --i)
arr[i] = arr[i - 1];
arr[i] = tmp;
}
}
- Inversion：对于一个序列 \(A\)，如果 \(i<j\) 且 \(A[i]>A[j]\)，则称 \((i, j)\) 是一个逆序对（inversion）
- 任何以交换逆序对为手段排序(称为简单排序)的算法平均复杂度 \(\Omega(N^2)\)
- 一趟插入排序可以消除一个逆序对
- 进行 \(n-1\) 趟（pass）排序
- 第 \(P\) 趟时保证从位置 0 到 \(P-1\) 上的元素以及排好序，然后将第 \(P\) 个元素插入到前面的有序序列的正确位置处
- 最坏（A 是逆序的）复杂度 \(O(N^2)\)
- 最好（A 是有序的）复杂度 \(O(N)\)
希尔排序¶
- 希尔排序（shell sort）使用一个增量序列 \(h_1<h_2<\cdots<h_t\)，其中 \(h_i\) 为整数，且 \(h_1=1\)
- 定义 \(h_k\)-sort 为将原数组隔 \(h_k-1\) 个元素分为一组，每组内进行排序
- \(k = t, t-1, \cdots, 1\) 依次进行 \(h_k\)-sort，最终得到一个有序序列
- \(h_k\)-sorted 的序列在 \(h_{k-1}\)-sorted 后仍保持 \(h_k\)-sorted 的性质
- 希尔排序的复杂度和增量序列的选取有关
-
希尔增量序列（原始版）：\(h_t=\lfloor N/2\rfloor, h_k = \lfloor h_{k+1}/2\rfloor\)
- 最坏复杂度 \(O(N^2)\)（即只在 1-sort 时进行了排序）
-
Hibbard 增量序列：\(h_k = 2^k-1\)
- 最坏复杂度 \(O(N^{3/2})\)
- 平均复杂度 \(O(N^{5/4})\)
堆排序¶
- 使用堆结构来进行排序
- 算法一：将数组中的元素依次插入到堆中（可以是 \(O(N)\) 线性建堆），然后依次从堆中取出最小元素
- 复杂度 \(O(N\log N)\)
- 但是空间消耗翻倍了(需要一个额外的数组来存排好的序列)
- 算法二：
- 以线性时间建最大堆（PercolateDown）
- 将堆顶元素与最后一个元素交换（相当于删除最大元素），然后进行 PercolateDown
- 依此循环，N-1 次删除后得到一个从小到大的序列
- 平均比较次数为 \(2N\log N - O(N\log\log N)\)
归并排序¶
- 关键的操作是合并两个有序列表变成一个有序列表，可以在 \(O(n)\) 时间内完成
- 归并操作则可以递归进行，分而治之，依次合并
- 复杂度：
\[
\begin{align*}
T(1) &= 1\\
T(N) &= 2T(\frac{N}{2}) + O(N)\\
&= 2^kT(\frac{N}{2^k})+k\cdot O(N)\\
&= N\cdot T(1) + \log N \cdot O(N)\\
&= O(N + N\log N) = O(N\log N)
\end{align*}
\]
代码
void mergeSort(int arr[], int n) {
int *tmp = malloc(sizeof(int) * n);
if (tmp != NULL) {
mergeSortHelper(arr, tmp, 0, n - 1);
free(tmp);
} else {
printf("No space for tmp array!\n");
}
}
void mergeSortHelper(int arr[], int tmp[], int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSortHelper(arr, tmp, left, center);
mergeSortHelper(arr, tmp, center + 1, right);
merge(arr, tmp, left, center + 1, right);
}
}
void merge(int arr[], int tmp[], int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos
int numElements = rightEnd - leftPos + 1;
while (leftPos <= leftEnd && rightPos <= rightEnd)
if (arr[leftPos] <= arr[rightPos])
tmp[tmpPos++] = arr[leftPos++];
else
tmp[tmpPos++] = arr[rightPos++];
while (leftPos <= leftEnd)
tmp[tmpPos++] = arr[leftPos++];
while (rightPos <= rightEnd)
tmp[tmpPos++] = arr[rightPos++];
for (int i = 0; i < numElements; ++i, rightEnd--)
arr[rightEnd] = tmp[rightEnd];
}
快速排序¶
- 已知的实际运行最快的排序算法
- 选择一个基准元素（枢轴 pivot），将数组分成两个子数组，左边的元素都小于等于基准元素，右边的元素都大于等于基准元素，然后对两个子数组进行快排、合并
- 选取 pivot
- 错误方法：pivot = arr[0]（对于排好序的数组仍会消耗 \(O(N^2)\) 的时间）
- 安全方法：pivot = random element in arr
- 但随机数生成也有开销
- 三数中值分割法：pivot = (left + center + right) / 3
- ~~划分策略~~（看不懂 PPT 在干什么）
- 小数组
- 对于小的 \(N\)（\(N\leq 20\)），快速排序慢于插入排序
- 可以在递归到 \(N\) 较小的情况下改为插入排序
- 最坏复杂度 \(O(N^2)\)
- 最优复杂度 \(O(N\log N)\)
- 平均复杂度 \(O(N\log N)\)
桶排序¶
- 如果输入数据都小于 \(M\)，则可以用一个大小为 \(M\) 的数组来记录某个值出现了多少次，这个数组称为桶（bucket）
- 桶初始化为 0，遍历输入数据，将每个数据对应的桶加 1
- 最后遍历桶中的所有元素，对于 bucket[x] = y，将 x 输出 y 次
- 时间复杂度 \(O(N+M)\)
基数排序¶
- 从低位（LSD，Least Significant Digit）到高位（MSB），对每一位进行进行排序
- 例如对 64, 8, 216, 512, 27, 729, 0, 1, 343, 125 进行排序
- 第一轮，按个位数排序
- 0, 1, 512, 343, 64, 125, 216, 27, 8, 729
- 第二轮，按十位数排序
- (0, 1, 8), (512, 216), (125, 27, 729), 343, 64
- 第三轮，按百位数排序
- (0, 1, 8, 27, 64), 125, 216, 343, 512, 729
- 完成排序
- 第一轮，按个位数排序
- 时间复杂度 \(O(P(N+B))\)，其中 \(P\) 为轮数，\(N\) 为元素个数，\(B\) 为桶个数
稳定性¶
- 对于一个序列，如果存在两个相等的元素
- 排序后它们的相对位置不变，则称这个排序算法是稳定的
- 排序后它们的相对位置发生了变化，则称这个排序算法是不稳定的
- 稳定排序：冒泡、归并、插入、基数
- 不稳定排序：快排、希尔、堆排、选择
最后更新:
2024年10月2日 14:45:20
创建日期: 2024年6月30日 01:05:46
创建日期: 2024年6月30日 01:05:46