几个排序算法的模板略解
本文最后更新于:2020年10月3日 上午
快速排序
- 快速排序是在数组中随机的找一个值,将比这个值小的数放在该数的左边,大的放在右边,然后左右分别递归。
- 将每次递归的左右端点设为
l, r
- 首先在数组中随机取一个值存放在
x
中,我直接取数组中间位置的值。int x = a[l + r >> 1]
(>>
是位运算) - 然后定义两个指针
i, j
分别从左往右和从右往左。 - 先将
i
从左往右移动,直到遇到一个比x
大的数就停下。j
相反。 - 然后判断
i < j
成立的话就交换两个数。
void qs(int l, int r) {
if (l >= r) return; //此时只有一个值,直接返回
int x = a[(r - l >> 1) + l]; //取中间值作为随机值
int i = l - 1, j = r + 1; //左右指针指向数组外面1的位置,方便后面操作
while (i < j) { //调整位置,知道i < j
while (a[++i] < x);
while (a[--j] > x);
if (i < j) swap(a[i], a[j]);
}
qs(l, j); //递归
qs(j + 1, r);
}
归并排序
- 二分数组,然后将排好序的左右数组合并成一个数组。
void ms(int l, int r) {
if (l >= r) return; //此时只有一个值,直接返回
int mid = (r - l >> 1) + l; //取中点
ms(l, mid); //左
ms(mid + 1, r); //右
int i = l, j = mid + 1, k = l; //两个指针分别指向左右的第一个位置
while (i <= mid && j <= r) tmp[k++] = a[i] < a[j] ? a[i++] : a[j++]; //比较指针位置大小,然后放进tmp,移动指针
//将剩下的放进tmp
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int i = l; i <= r; ++i) a[i] = tmp[i]; //排好序之后放回源数组
}
堆排序
- 维护一个完全二叉树,由于是完全二叉树,所以直接用一个数组来模拟不会浪费空间。根节点为
i
,左右分别为2*i
和2*i+1
- 该二叉树的根节点小于等于两个子节点。(递归定义)
- 定义一个
down
操作,将不满足上述定义的根节点向下移动。 - 先直接将所有数值放进数组中
- 然后将数组的前半段执行
down
操作(只需要操作前半段就可以排序整个数组)
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N], cnt, n, m;
void down(int u) {
int t = u, uu = u << 1; //计算根节点的2倍,减少后面的计算次数
if (uu <= cnt && h[uu] < h[t]) t = uu; //和左边比较
if (uu +1 <= cnt && h[uu + 1] < h[t]) t = uu + 1; //和右边比较
if (t != u) { //判断是否需要交换
swap(h[t], h[u]);
down(t);
}
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
cnt = n;
for (int i = n >> 1; i ; --i) down(i);
while (m--) {
printf("%d ", h[1]);
h[1] = h[cnt--];
down(1);
}
return 0;
}
六种排序算法的性能分析
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e4 + 10;
int a[N], a_bak[N], tmp[N], algo[N], n, m, cnt, all[6][M];
char name[6][15] = {"Quick Sort", "Merge Sort", "Heap Sort",
"Shell Sort", "Bubble Sort", "Select Sort"};
clock_t st, ed;
void init() {
srand(time(NULL));
for (int i = 1; i <= n; ++i) algo[i] = a[i] = a_bak[i] = rand();
a[0] = INT32_MIN;
sort(algo + 1, algo + n + 1);
}
//第x个算法的第y次测试
void judge(int x, int y) {
bool flag = 1;
for (int i = 1; i <= n; ++i)
if (a[i] != algo[i]) {
printf("%s\t Test %d Wrong Anwser\n", name[x], y);
flag = 0;
break;
}
if (flag) {
printf("%s\t Test %d Time Spent : %dms\n", name[x], y,
(int)(ed - st));
all[x][y] = (int)ed - st;
}
memcpy(a, a_bak, (n + 1) * sizeof(int));
}
//耗时分析
void analyze() {
double ave, max, min, sum;
for (int i = 0; i < 6; ++i) {
min = max = all[i][0];
sum = 0;
for (int j = 0; j < m; ++j) {
sum += all[i][j];
if (all[i][j] < min) min = all[i][j];
if (all[i][j] > max) max = all[i][j];
}
ave = sum / m;
printf("%s :\n Fastest : %.2lf\t Slowest : %.2lf\t Average : %.5lf\n\n",
name[i], min, max, ave);
}
}
// debug
void display() {
for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
puts("");
}
void quick_sort(int l, int r) {
if (l >= r) return;
int x = a[(r - l >> 1) + l];
int i = l - 1, j = r + 1;
while (i < j) {
while (a[++i] < x)
;
while (a[--j] > x)
;
if (i < j) swap(a[i], a[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = (r - l >> 1) + l;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int i = l; i <= r; ++i) a[i] = tmp[i];
}
// heap down操作
void down(int u) {
int uu = u << 1, t = u;
if (uu <= cnt && a[t] > a[uu]) t = uu;
if (uu + 1 <= cnt && a[t] > a[uu + 1]) t = uu + 1;
if (t != u) {
swap(a[t], a[u]);
down(t);
}
}
void heap_sort() {
int k = 1;
cnt = n;
for (int i = n >> 1; i; --i) down(i);
while (cnt) {
tmp[k++] = a[1];
a[1] = a[cnt--];
down(1);
}
for (int i = 1; i <= n; ++i) a[i] = tmp[i];
}
// 步长3
// void shell_sort(int n) {
// int h = 1;
// while (h < n / 3) h = 3 * h + 1;
// while (h >= 1) {
// for (int i = h; i < n; i++) {
// for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
// swap(a[j], a[j - h]);
// }
// }
// h = h / 3;
// }
// }
int get_sedgewick_arr(int n) {
int i = 0, j, k = 1;
while (true) {
j = 9 * ((1 << 2 * i) - (1 << i)) + 1;
if (j <= n) tmp[k++] = j;
j = (1 << 2 * i + 4) - 3 * (1 << i + 2) + 1;
if (j <= n)
tmp[k++] = j;
else
break;
i += 1;
}
return k;
}
// sedgewick步长
void shell_sort(int n) {
int k = get_sedgewick_arr(n);
int i, j, t, step;
while (--k) {
step = tmp[k];
for (i = step; i < n; ++i) {
j = i;
t = a[j];
while (j >= step) {
if (t < a[j - step]) {
a[j] = a[j - step];
j -= step;
} else
break;
}
a[j] = t;
}
}
}
void bubble_sort() {
for (int i = 1; i <= n; ++i)
for (int j = n - 1; j >= i; --j)
if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
void select_sort() {
int min;
for (int i = 1; i <= n; ++i) {
min = i;
for (int j = i + 1; j <= n; ++j)
if (a[j] < a[min]) min = j;
swap(a[i], a[min]);
}
}
int main() {
cin >> n >> m; //每组n个随机数,共测试m组
for (int i = 0; i < m; ++i) {
init();
int k = 6;
while (k--) {
st = clock();
switch (k) {
case 0:
quick_sort(1, n);
break;
case 1:
merge_sort(1, n);
break;
case 2:
heap_sort();
break;
case 3:
shell_sort(n + 1);
break;
case 4:
bubble_sort();
break;
case 5:
select_sort();
break;
}
ed = clock();
// display();
judge(k, i);
}
puts("=================================================\n");
}
analyze();
return 0;
}
输入n m
分别代表产生乱序数组长度和测试次数。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!