快速排序
不稳定
void quick_sort(int q[], int l, int r) {
if (l >= r) return;
// 位移和按位逻辑运算优先级低于加减
int i = l - 1, j = r + 1, pivot = q[l + r >> 1];
while (i < j) {
while (q[ ++ i] < pivot);
while (q[ -- j] > pivot);
if (i < j) swap(q[i], q[j]);
}quick_sort(q, l, j), quick_sort(q, j + 1, r);
}归并排序 【\\( O(n\log_{n}) \\)复杂度之排序】稳定
void merge_sort(int q[], int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0;
i <= r;
i ++, j ++ ) q[i] = tmp[j];
}希尔排序 不稳定
void shell_sort(int q[], int n) {
int i, j, gap;
for (gap = n / 2;
gap > 0;
gap /= 2)
for (i = gap;
i < n;
i ++ )
for (j = i - gap;
j >= 0 && a[j] > a[j + gap];
j -= gap)
swap(a[j], a[j + gap]);
}堆排序 不稳定
void down(int u) {
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t])
t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])
t = u * 2 + 1;
if (u != t) {
swap(h[u], h[t]);
down(t);
}
}void heap_sort(int h[], int n) {
for (int i = n / 2;
i;
i -- ) {
down(i);
}
int cnt = 1;
while (m -- ) {
ans[cnt ++ ] = h[1];
h[1] = h[n -- ];
down(1);
}
}
