原创 快速分类

2013-11-10 15:51 547 7 1

例如:  用A(m)划分集合A(m:P-1)

void Partition(m,p)
//在集合A(m),A(m+1),…,A(p-1)中的元素按如下方式重新排列:
//若最初t=A(m),则在重排完成之后,对于m和p-l之间的某个q,有A(q)=t,
//并使得对于m≤k<q,有A(k)≤t,而对于q<k<P,有A(k)≥t
//退出过程时,p带着划分元素所在的下标位置,即q的值返回。
eType a[n]; //定义为全局变量
int m,p,i;v=a[m];i=m; //A(m)是划分元素
while(i<p) {
do { i=i+1;} while(a<v) //i由左向右移,至少做一次。
do { p=p-1;} while(a

>v ) //p由右向左移,至少做一次。 if(i<p) {InterChange(a,a

);} //A(i)和A(p)换位 };//while a[m]=a

;a

=v; //划分元素在位置p }// Partition

 

有了划分集合A(m:P-1)的算法,使用分治策略可以设计出一个算法来对n个元素进行分类。随着对函数Partition的一次调用,就会产生出两个这样的集合S1和S2,S1的所有元素小于或等于S2的任何元素。因此S1和S2可独立分类。重复使用过程Partition,每个集合都将被分类。下列算法描述了这种分类的全过程。快速分类

void QuickSort(p,q)
//将全程数组A(1:n)中的元素A(p),…,A(q)按非递减的方式分类。
//认为A(n+1)已被定义,且大于或等于A(p:q)的所有元素,
//即假定A(n+1)为机器最大数。
int p,q;
eType a[n];int n; //定义成全程变量
if(q<q) {j=q+1;
Partition(p,j);
QuickSort(p,j-1); //j是划分元素的位置
QuickSort(j+1,q);
};//if
}//QuickSort

 

作者: 李肖遥, 来源:面包板社区

链接: https://mbb.eet-china.com/blog/uid-me-3912462.html

版权声明:本文为博主原创,未经本人允许,禁止转载!

PARTNER CONTENT

文章评论0条评论)

登录后参与讨论
EE直播间
更多
我要评论
0
7
关闭 站长推荐上一条 /3 下一条