基础算法
看ACWING崩溃一天
快速排序
点击查看代码
#include<iostream>
using namespace std;
const int N = 1e6+10;
int n;
int q[N];void quick_sort(int q[], int l, int r){// 递归终止条件：区间长度小于等于1时无需排序if(l >= r) return;// 初始化指针和基准值（取区间中间值作为基准，避免极端情况）int i = l - 1, j = r + 1, x = q[l + r >> 1];// 双指针遍历交换while(i < j){// i向右移动，直到找到大于等于x的元素do(i++); while(q[i] < x);// j向左移动，直到找到小于等于x的元素（修正了q[i]→q[j]和j++→j--）do(j--); while(q[j] > x);// 若i<j，交换两个元素if(i < j) swap(q[i], q[j]);}// 递归处理左右两个子区间quick_sort(q, l, j);quick_sort(q, j+1, r);
}int main(){// 输入数组长度scanf("%d", &n);// 输入数组元素for(int i = 0; i < n; i++) scanf("%d", &q[i]);// 调用快速排序quick_sort(q, 0, n - 1);// 输出排序后的数组（添加空格分隔）for(int i = 0; i < n; i++) printf("%d ", q[i]);return 0;
}
点击查看代码
#include<iostream>
using namespace std;
const int N = 100010;
int a[N] , tmp[N];
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;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];
}
int main(){int n ; scanf("%d" , &n);for(int i = 0 ; i < n; i++)scanf("%d" , &a[i]);merge_sort(a , 0 , n-1);for(int i = 0 ; i < n ; i++)printf("%d " , a[i]);return 0;}
点击查看代码
#include<iostream>
using namespace std;
const int N = 100010;
int q[N];
int n , m;int main(){scanf(" %d%d" , &n , &m);for(int i = 0 ; i < n ; i++)scanf("%d",&q[i]);while(m--){int x;scanf("%d" , &x);int l = 0, r= n -1;while(l < r){int mid = l + r >> 1;if(q[mid] >= x) r = mid;else l = mid + 1;}if(q[l] != x)cout << "-1 -1"<< endl;else{cout << l << ' ';int l = 0,r = n-1;while(l< r){int mid = l + r + 1 >> 1;if( q[mid] <= x) l = mid;else r = mid -1;}cout << l << endl;}}return 0;
}