8种排序算法汇总
- 快速排序
- 归并排序
- 堆排序
- 桶排序
- 冒泡排序
- 插入排序
- 选择排序
- 希尔排序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 106;
int n;
int a[N];
/* 排序算法汇总
* 排序算法 - 时间复杂度 - 空间复杂度 - 是否稳定
* 1. 快排 - O(n * log(n)) - O(n) - no
* 2. 归并 - O(n * log(n)) - O(n) - yes
* 3. 堆排序 - O(n * log(n)) - O(1) - no
* 4. 桶排序 - O(n) - O(c) - no
* 5. 冒泡排序 - O(n * n) - O(1) - yes
* 6. 插入排序 - O(n * n) - O(1) - yes
* 7. 选择排序 - O(n * n) - O(1) - no
* 8. 希尔排序 - O(n ^ {1.3 - 2}) - O(1) - no
*/
void down(int q[], int u) {
int t = u;
if ((u << 1) <= n && q[u << 1] < q[t]) t = u << 1;
if ((u << 1 | 1) <= n && q[u << 1 | 1] < q[t]) t = u << 1 | 1;
if (t != u) {
swap(q[t], q[u]);
down(q, t);
}
}
int stlunique(int q[]) {
return unique(q, q + n) - q;
}
int selunique(int q[]) {
int cnt = 1;
for (int i = 1; i < n; ++i) {
if (q[i] != q[cnt - 1]) {
q[cnt++] = q[i];
}
}
return cnt;
}
int selheapunique(int q[]) {
int tmp[N] = { q[1], }, cnt = 1;
q[1] = q[n--];
down(q, 1);
while (n) {
if (q[1] != tmp[cnt - 1]) {
tmp[cnt++] = q[1];
}
q[1] = q[n--];
down(q, 1);
}
for (int i = 0; i < cnt; ++i) {
q[i] = tmp[i];
}
return cnt;
}
void qsort(int q[], int l, int r) {
if (l >= r) return ;
int x = q[l + r >> 1], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
qsort(q, l, j);
qsort(q, j + 1, r);
}
// 1-1. stl快排
int stlqsort(int q[]) {
sort(q, q + n);
return stlunique(q);
}
// 1-2. 实现快排
int selqsort(int q[]) {
qsort(q, 0, n - 1);
return selunique(q);
}
void qsort3(int q[], int l, int r) {
if (l >= r) return ;
int x = q[l], lt = l - 1, gt = r + 1;
int i = l + 1;
while (i < gt && i <= r) {
if (q[i] == x) i++;
else if (q[i] < x) {
swap(q[i], q[lt + 1]);
lt++;
} else {
swap(q[i], q[gt - 1]);
gt--;
}
}
qsort3(q, l, lt);
qsort3(q, gt, r);
}
// 1-3. 三分区模式快排
int selqsort3(int q[]) {
qsort3(q, 0, n - 1);
return selunique(q);
}
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 k = 0, i = l, j = mid + 1;
int tmp[N];
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 (int i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];
}
// 2. 实现归并
int selmerge_sort(int q[]) {
merge_sort(q, 0, n - 1);
return selunique(q);
}
void heapsort(int q[]) {
for (int i = n; i; --i) {
q[i] = q[i - 1];
}
for (int i = n / 2; i; --i) {
down(q, i);
}
}
// 3. 实现堆排序
int selheapsort(int q[]) {
heapsort(q);
return selheapunique(q);
}
// 4. 桶排序
int bucketsort(int q[]) {
int hash[1006] = { 0 };
for (int i = 0; i < n; ++i) {
hash[q[i]]++;
}
int k = 0;
for (int i = 0; i < 1001; ++i) {
if (hash[i]) {
q[k++] = i;
}
}
return k;
}
// 5. 冒泡排序
int bubblesort(int q[]) {
for (int i = 0; i < n - 1; ++i) {
bool isSwap = false;
for (int j = 0; j < n - i - 1; ++j) {
if (q[j] > q[j + 1]) {
swap(q[j], q[j + 1]);
isSwap = true;
}
}
if (!isSwap) break;
}
return selunique(q);
}
// 6. 插入排序
int InsertSort(int q[]) {
for (int i = 1; i < n; ++i) {
for (int j = i; j; --j) {
if (q[j] < q[j - 1]) {
swap(q[j], q[j - 1]);
} else break;
}
}
return selunique(q);
}
// 7. 选择排序
int SelectSort(int q[]) {
for (int i = 0; i < n - 1; ++i) {
int t = i;
for (int j = i + 1; j < n; ++j) {
if (q[j] < q[t]) {
t = j;
}
}
if (i != t) swap(q[t], q[i]);
}
return selunique(q);
}
// 8. 希尔排序
int ShellSort(int q[]) {
for (int len = n; len; len >>= 1) {
for (int s = 0; s < len; ++s) {
for (int i = s + len; i < n; i += len) {
for (int j = i; j > s; j -= len) {
if (q[j] < q[j - len]) {
swap(q[j], q[j - len]);
} else break;
}
}
}
}
return selunique(q);
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
int k;
// k = stlqsort(a);
// k = selqsort(a);
// k = selqsort3(a);
// k = selmerge_sort(a);
// k = selheapsort(a);
// k = bucketsort(a);
// k = bubblesort(a);
// k = InsertSort(a);
// k = SelectSort(a);
k = ShellSort(a);
cout << k << endl;
for (int i = 0; i < k; ++i) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}
tql
很不错 给汇总点赞 👍
八核学习八倍快乐即视感