排序入门

it2022-05-07  8

排序:外部排序,内部排序

以下内容 无须铭记 内部排序是在内存中进行排序 外部排序 当文件较大,内存无法全部储存,将文件存放在外面,使用......方法让文件依次进入内存排序 我们接触到的排序都是内部排序

bogo排序:随机打乱,检查是否有序。

srand(time(NULL)) for(;;){ //while(1) bool pd=1; for(i:1->n-1) if(a[i]>a[i+1]){ pd=0; break; } if(pd) break; for(i:1->n) { int j=rand()%n+1; swap(a[i],a[j]); } // random_shuffle(a+1,a+n+1); }

------------------------------------华------丽------的------分------割------线-------------------------------------

八大排序:

插入排序: 直接插入排序,希尔排序 选择排序:简单选择排序,堆排序

交换排序:冒泡排序,快速排序

归并排序

基数排序

—————————————————————————————————————————————————————————— 简单介绍以下各种排序: 直接插入排序:从未排序的数中依次枚举,插入到已排序的序列中

for(int i=2;i<=n;++i){ int j=i-1; int tmp=a[i]; while(j&&a[j]>tmp) a[j+1]=a[j],j--; if(j!=i-1) a[j+1]=tmp; } //时间复杂度:O(n^2) //空间复杂度:O(n) //稳定排序

希尔排序:插入排序改进版,选择一个增量d,将d的倍数放在一组,进行插入排序

for(int d=n/2;d;d>>=1) { for(i=d;i<=n;++i) { int j=i-d; int tmp=a[i]; while(j>0&&a[j]>tmp) a[j+d]=a[j],j-=d; if(j+d!=i) a[j+d]=tmp; } } //时间复杂度:O(玄学)(最优O(n^1.3)) //空间复杂度:O(n) //不稳定排序

简单选择排序:在未排序数列中,找出最小的数与第一个交换,再在未排序数列中,找出最小的数与第二个交换

简单选择排序: for(int i=1;i<=n;++i){ int k=i; for(j=i+1;j<=n;++j) if(a[j]<a[k]) k=j; swap(a[k],a[i]); } //时间复杂度:O(n^2) //空间复杂度:O(n) //不稳定排序

冒泡排序:不断交换相邻两个值

for(int i=1;i<n;++i){ bool change=0; for(j=1;j<n-i;++j) if(a[j]>a[j+1]) swap(a[j],a[j+1]); if(!change) break; } //时间复杂度:O(n^2) //空间复杂度:O(n) //稳定排序

附: 鸡尾酒排序:双向冒泡排序排序

int l=1,r=n; while(l<r){ for(i=l;i<r;++i) if(a[i]>a[i+1]) swap(a[i],a[i+1]); r--; for(i=r;i>l;--i) if(a[i-1]>a[i]) swap(a[i-1],a[i]); l++; } //时间复杂度:O(n^2) //空间复杂度:O(n) //稳定排序

桶排:不常用但很好用,将所有的数放入到桶中,依次取出

int Max=0,Min=oo; for(int i=1;i<=n;++i) t[a[i]]++,Max=max(Max,a[i]),Min=min(Min,a[i]); for(int i=Min;i<=Max;++i) while(t[i]) a[++cnt]=i,t[i]--; //时间复杂度:O(max_num) //空间复杂度:O(n+max_num) //不稳定排序

—————————————————————————————————————————————————————————— 当然,除了堆排序、快速排序、归并排序、基数排序,其余的基本不用

堆排序 维护堆,将 数据放入一个堆中 依次取出 实现 : 大根堆 priority_queue 如 : priority_queue\(<int>\) 小根堆 priority_queue<数据类型,容器,比较函数> 如 : priority_queue<int,vector \(<int>\) ,greater \(<int>\) > (注:greater<> 是c++标准模板库(STL) 自带比较函数)

priority_queue<int> q;//priority_queue<int,vector<int>,greater<> > q; for(int i=1;i<=n;++i) q.push(a[i]); while(!q.empty()) a[++cnt]=q.top(),q.pop(); //时间复杂度:O(nlogn) //空间复杂度:O(n) //不稳定排序

———————————————————————————————————————————————————————————

归并排序 不断递归二分,使子区间有序,在合并成一个大区间

void Merge_sort(int l,int r){ if(l==r) return ; int mid=l+r>>1; Merge_sort(l,mid); Merge_sort(mid+1,r); int i=l,j=mid+1,cnt=0; while(i<=mid&&j<=r) if(a[i]<=a[j]) b[++cnt]=a[i++]; else b[++cnt]=a[j++]; while(i<=mid) b[++cnt]=a[i++]; while(j<=r) b[++cnt]=a[j++]; for(i=1;i<=cnt;++i) a[l+i-1]=b[i]; } //时间复杂度:O(nlogn) //空间复杂度:O(2n) //稳定排序

———————————————————————————————————————————————————————————

快速排序 以 小-->大 排序 二分,选择一个基准,在基准左边选一个小于基准的元素 在右边选一个大于基准的元素 交换 再递归,分别对左右区间操作,将大于基准的放在基准右边 小于基准的放在基准左边

实现 : 小-->大 sort(a+1,a+n+1); (区间是 左闭右开) 大-->小 sort(a+1,a+n+1,greater\(<int>\)()) 防止相同元素改变顺序:stable_sort();

void Quick_sort(int l,int r){ int mid=a[l+r>>1]; int i=l,j=r; while(i<=j) { while(a[i]<mid) i++; while(a[j]>mid) j--; if(i<=j) swap(a[i],a[j]),i++,j--; } if(i<r) Quick_sort(i,r); if(j>l) Quick_sort(l,j); } //时间复杂度:O(nlogn) //空间复杂度:O(n) //不稳定排序

————————————————————————————————————————————————————————————

基数排序 按位 (从低位到高位) 排序, 以 小-->大 排序 从低位--高位 按每一位 由小到大进行排序,具体实现可用通排

void BCN_sort(int n,int Max_len){ int t[10][Max]={0}; int k=1,m=1,cnt=1; while(k<Max_len){ for(i=1;i<=len;++i){ if(a[i]<m) t[0][cnt]=a[i]; else { int pos=a[i]/m; t[pos][cnt]=a[i]; } cnt++; } Collect(a,t); cnt=0; m*=10; k++; } } //时间复杂度:O(Max_len*n) //空间复杂度:O(10*n) //稳定排序

————————————————————————————————————————————————————————————

用堆来排序并不多见,因为堆是可以支持O(1)查询 O(log n)插入、删除 所以 在一些取最值的题目中,才能体现他的优势

快排是OI中用的最多的排序,标准模板库中的 sort 与自己写的快速排序要快得多,尽管它是STL 况且,你可你自己写比较函数来改变 sort 的比较键值(Key) 虽然它不稳定,但应该不会有人要出数据去卡快速排序 至于快排的另一用法 查询某一元素在序列中是第几大,也可以用 nth_element() 来实现

基数排序,也不常用,讲它的是因为 后缀数组(SA) 中会用到它

归并排序 本来不想讲,它虽然稳定,真不常用,但他的思想非常重要,在CDQ分治中它起着很大作用

————————————————————————————————————————————————————————————

排序应用:去重、离散化

去重:排序后 保留当前元素和前一个元素不同的

void Unique(){ sort(a+1,a+n+1); int cnt=0; for(int i=1;i<=n;++i) if(a[i]!=a[i-1]) b[cnt++]=a[i]; }

离散化:一个大区间有许多浪费的位置,而且我们只需要它们的大小关系,可以将它们按大小重新编号

struct array{ int Ori_num,Now_num,id; friend bool operator < (array x,array y){ return x.Ori_num<y.Ori_num; } }a[N]; boold comp(array x,array y){ return x.id<y.id; } void Discre{ sort(a+1,a+n+1); int cnt=0; for(int i=1;i<=n;++i) if(a[i].Ori_num!=a[i-1].Ori_num) a[i].Now_num=++cnt; sort(a+1,a+n+1,comp); } for(int i=1;i<=n;++i) scanf("%d",&a[i]),pos[i]=a[i]; sort(pos+1,pos+n+1); int m=unique(pos+1,pos+n+1)-pos-1; for(int i=1;i<=n;++i) b[i]=lower_bound(pos+1,pos+m+1,a[i])-pos;

———————————————————————————————————————————————————————————— 简单题:佳佳的魔法照片

转载于:https://www.cnblogs.com/heower/p/8467707.html


最新回复(0)