选择排序(SelectionSort)
每次从没有排好的范围中挑出最大或最小值,放入已经排好的数列最前或最后的位置。
时间上最内层的单条语句的执行次数可表示为 $\displaystyle\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} n-2k = (n-1-\lfloor\dfrac{n}{2}\rfloor)\lfloor\dfrac{n}{2}\rfloor \leq o(\lfloor\dfrac{n}{2}\rfloor^2) \leq o(n^2)$。
事实上由于最内层执行两次,总的复杂度不会是 $o(\lfloor\dfrac{n}{2}\rfloor^2)$,但一定是 $o(n^2)$ 的量级。
空间上由于和问题规模无关,所以 $O(1)$。
/* 假设要求以单调递增的顺序排好序。*/
void swapContent(int a[], int x, int y) {
a[x] ^= a[y];
a[y] ^= a[x];
a[x] ^= a[y];
}
// a[0...sizer-1]
void SelectionSort(int a[], size_t sizer) {
for (size_t tt = sizer-1, hh = 0; tt > hh; tt --, hh ++) {
int pmaxn = hh, pminn = hh;
for (size_t j = hh; j <= tt; j ++) {
if (a[pmaxn] < a[j])
pmaxn = j;
if (a[pminn] > a[j])
pminn = j;
}
swapContent(a, tt, pmaxn);
swapContent(a, hh, pminn);
}
}
桶排序(BucketSort)
假设内存空间足够,且数列的分布均已知。一种更快的做法是将数值作为索引,累计对应数值在数列中出现的次数。
int pos_shift = 0x100;
size_t bucket_size = 114514;
void BucketSort(int a[], size_t sizer) {
for (size_t i = 0; i < sizer; i ++)
tmpArr[a[i] + pos_shift] ++;
for (size_t i = 0; i < bucket_size; i ++)
while (tmpArr[i] --)
printf("%d ", i - pos_shift);
}
冒泡排序(BubbleSort)
在严格递增的要求下,相邻两两比较,每次都将逆序的一个与邻居换位,直到不能再换为止。
优化:已经有序的就不需要比较。都没有变化的就已经排好,退出即可。当然还可以最大最小两端同时进行,与上文的选择排序做相同的事情。因道理一致,此处不做实现。
时间:$o(n^2)$。
空间:$o(1)$。
void BubbleSort(int a[], size_t sizer) {
for (size_t i = sizer-1; i >= 0; i --) {
char ok = 0;
for (size_t j = 0; j < i; j ++)
if (a[j] > a[j+1]) {
swapArr(a, j, j+1);
ok = 1;
}
if (!ok) break;
}
}
堆排序(HeapSort)
小根堆的定义: $\forall i \in \{0, 1, \ldots, n-1\}, \begin{cases} a_{i} \leqslant a_{2i} \\ a_i \leqslant a_{2i + 1}\end{cases}$。其中 $a_{i}$ 表示表中第 $i$ 个元素的值。
大根堆只需对调小于等于号。
将序列视为完全二叉树的一部分。那么这一排序算法能成功的缘由是可通过调整树满足定义,逐级筛出最小值。每取一次就交换根节点和最后一个节点并调整整棵树。
查询、建立、删除的时间复杂度均为 $o(n\log n)$。
inline void swapVal(int a[], int x, int y) {
a[x] ^= a[y];
a[y] ^= a[x];
a[x] ^= a[y];
}
void down(int a[], int pos, int constrain) {
// 比较自己与两个孩子,然后递归到最后。
int lc = pos << 1, rc = pos << 1 | 1, choice = pos;
// 建立小根堆。
if (lc <= constrain && a[lc] < a[choice]) {
choice = lc;
}
if (rc <= constrain && a[rc] < a[choice]) {
choice = rc;
}
if (choice == pos) return;
swapVal(a, pos, choice);
down(a, choice, constrain);
}
void BuildHeap(int a[], int constrain) {
for (int i = constrain >> 1; i; i --) {
down(a, i, constrain);
}
}
void HeapSort(int a[], int constrain) {
BuildHeap(a, constrain);
for (int i = constrain, j = 1; i; i --, j ++) {
printf("%d ", a[1]);
swapVal(a, 1, i);
down(a, 1, constrain - j);
}
}
不难发现核心的 down
函数是尾递归。可以转成非递归版本,于是就能做到 $o(1)$ 的空间复杂度。
int arr[100086];
void swapVal(int a[], int x, int y) {
a[x] ^= a[y];
a[y] ^= a[x];
a[x] ^= a[y];
}
void down(int a[], int fa, int limitation) {
int lc = fa << 1, rc = fa << 1 | 1, choice = fa;
while (true) {
if (lc <= limitation && a[lc] < a[choice]) choice = lc;
if (rc <= limitation && a[rc] < a[choice]) choice = rc;
if (choice == fa) return;
swapVal(a, fa, choice);
fa = choice;
lc = fa << 1, rc = fa << 1 | 1;
}
}
int heapSort(int a[], int len) {
for (int i = len >> 1; i; i --) pushup(a, i, len);
for (int i = len; i; i --) {
a[0] = a[1];
swapVal(a, 1, i);
pushup(a, 1, i - 1);
}
swapVal(a, 0, 1);
}
// 之后倒序输出即可。
堆排序可用于求解 TOP $k$,当 $k$ 的数量远小于数据数量时,即可通过维护最小值的大根堆或者最大值的小根堆来完成。这在内存不够的情形下具有显著的优势。
归并排序(MergeSort)
两路有序序列,每次从队头抽出最小值。最后再抽出剩余没比完的即可。
递归能成立的前提是至少要 $1$ 对 $1$ 的比。那么这样就产生了长度为 $2$ 的有序序列。之后就能与邻居构成更大的有序序列,以至于能完全覆盖到原始无序的序列。
所谓多路就是有多个有序序列,每次只需要根据队头的值维护一个败者树即可。
int tmp[114514];
// [l, r]
long long mergeSort(int a[], int l, int r) {
if (l >= r) return 0;
int mid = (l + r) >> 1;
long long lres = mergeSort(a, l, mid);
long long rres = mergeSort(a, mid+1, r);
long long i = l, j = mid + 1, cnt = 0, res = 0;
while (i <= mid && j <= r) {
char curr = a[i] <= a[j];
tmp[cnt++] = a[curr ? i++ : j ++];
res += curr ? 0 : mid - i + 1;
}
while (i <= mid) tmp[cnt++] = a[i++];
while (j <= r) tmp[cnt++] = a[j++];
for (int k = 0; k < cnt; k ++)
a[l+k] = tmp[k];
return lres + rres + res;
}
快速排序(QuickSort)
由于枢轴两侧与枢轴本身的偏序关系得到保证,即左部小于枢轴小于右部,因此可以递归地完成这一问题。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int a[100086];
void quickSort(int a[], int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
int x = a[mid], i = l - 1, j = r + 1;
while (i < j) {
do i ++; while (a[i] < x);
do j --; while (a[j] > x);
if (i < j) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
}
quickSort(a, l, i - 1);
quickSort(a, j + 1, r);
}
第 $k$ 大数问题。本质上是计算 $k$ 相对于枢轴的位置。唯一要注意的是快排中途可能会在不同情况下出现的两种情况。这影响了最终对答案的求取。
int quickSort(int a[], int l, int r, int pos) {
if (l >= r) return a[l];
int mid = (l + r) >> 1;
int x = a[mid], i = l - 1, j = r + 1;
while (i < j) {
do i ++; while (a[i] < x);
do j --; while (a[j] > x);
if (i < j) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
}
/* i-1
|i
1: +++++++++ (i == j)
j+------> j + 1
j|
2: +++++++++ (j < i)
|i
i-1
*/
if (pos < i)
return quickSort(a, l, i - 1, pos);
else if (pos > j)
return quickSort(a, j + 1, r, pos);
else
return a[i];
}
某考试有时出的题目可能会 非常弱智 地将枢轴定在第一个元素,故意造成算法的恶化。
二分插入排序(InsertationSort)
插入排序就像洗牌一样,逐个按顺序将左手上的牌插入到正确的位置。在小数据量的情况下人能够在 $o(n)$ 完成插入。对于计算机而言,由于前面的序列都已正确,每次排序只需要找到位置插入即可。
不过,由于不存在可通过索引来 $o(1)$ 插入的数据结构,所以最坏情况下的插入,时间复杂度可表示为 $o(\displaystyle\sum_{i=1}^{n}i)=o(n^2)$。
这里提供两种写法
for (int i = 1 ; i <= n; i ++)
scanf("%d", a + i);
for (int i = 2; i <= n; i ++) {
int ll = 1, rr = i, mid = (ll + rr) >> 1, tmp = a[i];
while (ll < rr) {
mid = (ll + rr) >> 1;
if (a[mid] > a[i]) rr = mid;
else if (a[mid] < a[i]) ll = mid + 1;
else break;
}
mid = (ll + rr) >> 1;
for (int j = i; j > mid; j --)
a[j] = a[j - 1];
a[mid] = tmp;
}
for (int i = 0; i < n; i ++)
scanf("%d", a + i);
for (int i = 1; i < n; i ++) {
int j = i - 1, now = a[i];
auto idx = std::upper_bound(a, a + i, now) - a;
while (j >= idx) {
a[j + 1] = a[j]; j --;
}
a[j + 1] = now;
}
for (int i = 0; i < n; i ++)
printf("%d ", a[i]);
希尔排序(ShellSort)
将整个数列按照给定的组长划分。组和组之间按列的位置做插入排序。每排完一趟就缩小组长。直到做完组长为 $1$ 的插入排序时整个序列就有序。
时间上复杂度只能说与划分的组数有关,同时因排序不能保证相同数字的位置保持不变,所以此排序算法不稳定。
算法的正确性仰仗于每次排序构造的 $a_i \leq a_{i+s}$,其中 $s$ 表示组长。
如果下一趟组长变为 $t$,则 $a_i \leq a_{i + t} \leq a_{i + t + s}, i \leq \min(s, t)$ 能保证成立。
感兴趣可以阅读1。
以下的实现可以以较大的常数通过基础课中的归并排序。
for (int i = 1; i <= n; i ++)
scanf("%d", a + i);
for (int step = n >> 1; step; step >>= 1) {
for (int st = 1; st <= step; st ++) {
for (int j = st + step; j <= n; j += step) {
int ll = 0 /* st + 0 * step, 0 */,
rr = (j - st) / step /* st + p * step, p */;
int mid = (ll + rr) >> 1, tmp = a[j];
while (ll < rr) {
mid = (ll + rr) >> 1;
int temp = st + mid * step;
if (a[temp] > tmp) rr = mid;
else if (a[temp] < tmp) ll = mid + 1;
else break;
}
mid = (ll + rr) >> 1;
int choice = st + mid * step;
for (int k = j; k > choice; k -= step)
a[k] = a[k - step];
a[choice] = tmp;
}
}
}