选择排序(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 swapVal(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;
}
swapVal(a, tt, pmaxn);
swapVal(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 --) down(a, i, len);
for (int i = len; i; i --) {
a[0] = a[1];
swapVal(a, 1, i);
down(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;
}
// leetcode.cn/problems/merge-k-sorted-lists/
// 败者树。可通过类似线段树的方式构建。抽取时每次弹出根以更新所在的队列，每弹一次就要更新树。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
**/
const short inf = 0x7F7F;
typedef struct _node_info { short val, pos; } node_info;
node_info tr[10086 * 4]; // 0 < k < 1e4
inline void _up(short curr) {
auto lf = tr[curr << 1], rf = tr[curr << 1 | 1];
tr[curr] = lf.val < rf.val ? lf : rf;
}
void _build(vector<ListNode*>&vec, short curr, short l, short r) {
if (l == r) {
tr[curr] = {vec[l] == nullptr ? inf : (short)(vec[l]->val), l};
return;
}
short mid = (r + l) >> 1;
_build(vec, curr << 1, l, mid), _build(vec, curr << 1 | 1, mid + 1, r);
return _up(curr);
}
void _update(short target, short choice, short curr, short l, short r) {
if (l == r) {
tr[curr] = {choice, target};
return;
}
short mid = (r + l) >> 1;
if (target <= mid)
_update(target, choice, curr << 1, l, mid);
else
_update(target, choice, curr << 1 | 1, mid + 1, r);
return _up(curr);
}
void sorter(vector<ListNode*> lists) {
if (lists.size() == 0)
return;
vector<ListNode*> tmp;
tmp.push_back(nullptr);
for (auto p: lists)
tmp.push_back(p);
_build(tmp, 1, 1, tmp.size()-1);
int i = 0;
ListNode *res = nullptr, *tail, *work;
while (tr[1].val != inf) {
if (!i) {
res = new ListNode;
res->val = tr[1].val;
tail = res;
} else {
work = new ListNode;
work->val = tr[1].val; // 使已有链表连接到 tail
tail->next = work; // 尾插。
tail = work;
}
short choice = inf, now = tr[1].pos;
if (tmp[now] != nullptr) {
tmp[now] = tmp[now] -> next;
if (tmp[now] != nullptr)
choice = tmp[now] -> val;
}
_update(tr[1].pos, choice, 1, 1, tmp.size()-1);
i ++;
}
}
// 也可以将多个有序队列每两个合并为一个，直到最终只有一个有序队列。
// 此处不做实现。
快速排序(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
|/
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;
}
}
}
