笔记大合集
$$持续更新ing$$
一.快速排序
主要思想:分治
1.确定分界点:左边界 $q[l]$ , 中间值(平均值) $q[(l+r)>>1]$ , 右边界 $q[r]$ ,随机
2.调整区间
3.递归处理左右两段
问题:$>>1$ 是什么意思?就是除以 $2$ 的意思 ,是位运算符
那为什么要用 $>>1$ 呢?因为题目数据加强
时间复杂度 $O(n log n)$
模板题
void d(int q[],int l,int r)
{
if(l>=r)return;
int i=l-1,j=r+1,x=q[l+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]);
}
d(q,l,j);
d(q,j+1,r);
}
为快速排序模板
二.归并排序
主要思想-分治
1.确定分界点 $mid=(l+r>>1)$
2.递归排序
3.归并-合二为一
时间复杂度 $O(nlogn)$
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 (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
算法模板
模板题
三. $sort$ 语法
当然前面两种算法都可以直接改成 $sort$
从小到大排序
#include<bits/stdc++.h>
using namespace std;
int b[114514];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>b[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)cout<<b[i]<<" ";
return 0;
}
%%%我只会bubble-sort555