首页 > 代码库 > 【分治】简单说说快排
【分治】简单说说快排
说到快拍,大家都会首先想到sort函数这个神奇的东西
但是,我们总得知道快拍主要用的分治思想
所以就说一说快拍吧
首先是分类
快拍主要有三种方式:
一、以第一个数为基准排序
二、以中间的数为基准快排
三、随机生成一个位置,用这个位置上的数快排
代码如下:
#include<cstdio> #include<algorithm> #include<iostream> #include<cstdlib> #include<ctime> using namespace std; int n,a[2000002]; /*int rrand(int l,int r) //三中用于生成随机位置 { srand((unsigned)time(NULL)); return (int)(rand()%(r-l+1)+l); }*/ void qsort(int l,int r) //以中间的数为基准快排 { int i,j,mid,p; i=l;j=r; mid=a[(l+r)/2]; do { while(a[i]<mid) i++; while(a[j]>mid) j--; if(i<=j) { p=a[i]; a[i]=a[j]; a[j]=p; i++; j--; } }while(i<=j); if(l<j) qsort(l,j); if(i<r) qsort(i,r); } /*void qsort(int l,int r) //随机&首位快排 { int i=l,j=r+1,temp=rrand(l,r),k=0; //首位的话是temp=a[i] if(r-l<2) return; while(i<j) { while(i<j) { j--; if(a[j]<temp) { swap(i,j); break; } } while(i<j) { i++; if(a[i]>temp) { swap(i,j); break; } } } a[i]=temp; qsort(l,i); qsort(i+1,r); } */ int main() { freopen("sorttest.in","r",stdin); freopen("sorttest.out","w",stdout); scanf("%d",&n); for(int i=n;i>=1;i--) scanf("%d",&a[i]); /*sort(a+1,a+n+1); //喜闻乐见的sort for(int i=1;i<=n;++i)printf("%d ",a[i]); */ qsort(1,n); for(int i=1;i<=n;++i)printf("%d ",a[i]); fclose(stdout); return 0; }
【分治】简单说说快排
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。