疾速排序
不稳固
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);}归并排序
稳固
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); }}