排序算法模板(更新中)
2023-04-18 15:23:08 时间
快速排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void position(int q[], int l, int r){
if (l >= r) return ; // 边界
int x = q[l], i = l-1, j = r+1;
while(i < j) {
while (q[++i] < x); // 从左往右扫描
while (q[--j] > x); // 从右往左扫描
if(i < j) {
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
position(q, l, j); // 对左区间排序
position(q, j + 1, r); // 对右区间排序
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &q[i]);
position(q, 0, n-1);
for(int i = 0; i < n; i++)
printf("%d ", q[i]);
return 0;
}
归并排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
int n, a[N], temp[N];
void position(int a[], int l, int r){
if(l >= r) return ;
int mid = l + r >> 1;
// 递归
position(a, l, mid), position(a, mid+1, r);
int k = 0, i = l, j = mid+1;
// 归并
while(i <= mid && j <= r)
if(a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
// 收尾
while(i <= mid) temp[k++] = a[i++];
while(j <= r) temp[k++] = a[j++];
// 整合成一个有序序列
for(i = l, j = 0; i <= r; i++, j++)
a[i] = temp[j];
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
position(a, 0, n-1);
for(int i = 0; i < n; i++) {
cout << a[i] << " ";
}
return 0;
}
解法:
- 区间[L, R] => [L, mid] 和 [mid + 1, R]
- 递归排序[L, mid] 和 [mid + 1, R]
- 归并,将左右两个有序序列合并成一个有序序列
归并排序----逆序对的数量
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, q[N], temp[N];
LL position(int l, int r){
if(l >= r) return 0;
int mid = l + r >> 1;
LL teg = position(l, mid) + position(mid+1, r);
int k = 0, i = l, j = mid+1;
while(i <= mid && j <= r){
if(q[i] <= q[j])
temp[k++] = q[i++];
else {
temp[k++] = q[j++];
teg += mid - i +1 ;
}
}
while(i <= mid)
temp[k++] = q[i++];
while(j <= r)
temp[k++] = q[j++];
for(i = l, j = 0; i <= r; i++, j++)
q[i] = temp[j];
return teg;
}
int main() {
cin >> n;
for(int i = 0; i < n; i++)
cin >> q[i];
cout << position(0, n-1) << " ";
return 0;
}
思路:
使用归并排序解题时,逆序对分为三种情况:全在左区间;全在右区间;一个在左区间一个在右区间。对于第三种情况,当左区间(已排序)的一个数i刚好大于右区间的一个数j,那么mid+1 >= i 的数都大于j,就可以得出teg = mid - i + 1.
// 插入排序
void insertSort(int a[], int len){
for(int i = 1; i < len; i++){
int temp = a[i];
int j = i - 1;
while( j >= 0 && a[j] > temp){
a[j+1] = a[j];
j--;
a[j+1] = temp;
}
}
}
// 冒泡排序
void bublleSort(int a[], int len){
int flag = 1;
while(flag){
flag = 0;
for(int i = len - 1; i > 0; i--){
if(a[i] < a[i-1]){
swap(a[i], a[i-1]);
flag = 1;
}
}
}
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击