Pixiv - Miracle
2-排序
448 字
2 分钟
2-排序
排序
- 插排外层循环为插入键值内层循环为有序部分右移
- 选排外层排序记录有序部分末尾内层循环找最小值，
- 冒排外层循环进行n次内循环，内层循环做相邻交换
- 快排外循环左右找到第k个关于x的逆序，内循环交换消除逆序,并迭代
- 归并排序能求逆序对数量
- 堆排，用处不大
归并排序
#define N 1000
int tmp[N];void ms(int q[], int l, int r) { if (l >= r) return;
int m = l + r >> 1;
ms(q, l, m), ms(q, m + 1, r);
int i = l, j = m + 1, k = 0; while (i <= m && j <= r) { if (q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++];// 这里可以统计以q[j]为结尾的逆序对数量，全部加起来就是逆序对数量 }
while (i <= m) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++];
for (int i = l, j = 0; i <= r; ++i) q[i] = tmp[j++];}快速排序
当x = q[r]时，若元素在2个及以上，若采用l, j | j + 1, r,则由于j可能在j=r直接停止，[r+1, r]是空集，[l, r]是原来的区间，即一次快排可能产生相同的一次快排和一个空集，产生死循环
void qs(int q[], int l, int r) { if (l >= r) return;
int i = l - 1, j = r + 1, x = q[(i + j) >> 1]; while (i < j) { do ++i; while (q[i] < x); do --j; while (q[j] > x); if (i < j) swap(q[i], q[j]); }
qs(q, l, j), qs(q, j + 1, r);}冒泡排序
void bubbleSort(int q[], int l, int r) { for (int i = l; i <= r; ++i) { bool swapped = 0; for (int j = l + 1; j <= r - (i - l); ++j) { if (q[j - 1] > q[j]) {swap(q[j - 1], q[j]); swapped = 1;} } if (!swapped) break; }}文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
随机文章 随机推荐