快速排序 - 推酷
快速排序(QuickSort)
1、算法思想
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
&&& 分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
（2）快速排序的基本思想
&&& 设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
在R[low..high]中任选一个记录作为基准(Pivot)（通常选择第一个数组元素作为基准），以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
&&& 划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
&&& R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
&&&&&&&&&&&&&&&&& 其中low≤pivotpos≤high。
调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
因为当&求解&步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，&组合&步骤无须做什么，可看作是空操作。
2、快速排序算法QuickSort
& void QuickSort(SeqList R，int low，int high)
&& { //对R[low..high]快速排序
&&&& int pivotpos； //划分后的基准记录的位置
&&&& if(low&high){//仅当区间长度大于1时才须排序
&&&&&&& pivotpos=Partition(R，low，high)； //对R[low..high]做划分
&&&&&&& QuickSort(R，low，pivotpos-1)； //对左区间递归排序
&&&&&&& QuickSort(R，pivotpos+1，high)； //对右区间递归排序
&&& } //QuickSort
&&& 为排序整个文件，只须调用QuickSort(R，1，n)即可完成对R[l..n]的排序。
3、划分算法Partition
下面介绍两种划分的解决思路：
这两种划分的过程都需要用到两个指针i,j(指示数组下标)；并且
假定每次都指定数组的第一个元素作为基准
（1）i,j下标同时从左往右走。
& i和j初始同时指向基准，以后j指针一直向右走，如果j所指向的元素小于或者等于基准（第一个元素），那么i也向右走一步。
（这个时候我们可以这样理解 i 这个指针，它表示在其所指向元素的左边（包括本身）都小于等于基准。）
那么如果 j 所指向的元素大于基准，那么 i 指针不动。
那么就可能出现这样的情况：
这个时候 指针 i 和 j 之间间隔了几个元素，那怎么办呢？&
这样的话，先 i++； &然后把 i 所指向的元素 &和 &j 所指向的元素互换，这样就ok了。
按照这样一直做下去，直到 指针 j &指到最后一个元素结束；
最后再 &交换 第一个元素（也就是基准） 和 &指针 i &所指向的元素。&
下面展示一下，用c++实现的代码：
void swap(int &a, int &b)
int split_1(int* a,int low,int high)
int i = 0;
int x = a[low];
for(int j = 1; j&= j++)
if(a[j] &= x)
if(i != j)
swap(a[i],a[j]);
swap(a[low],a[i]);
i,j下标分别在最左端和最右端，同时往中间走。
初始状态如下：
&指针 i &向右扫描，直到所指向的元素大于基准值；
&指针 j &向左扫描，直到所指向的元素小于基准值。
那么这个时候，指针 i &所指向的元素大于基准值； 指针 j &所指向的元素小于基准值。
&指针 i 所指向元素 & 和 & 指针 j 所指向元素。
一直重复上述过程，直到，指针 &i & 跑到 &指针 &j &的右边。
& & & &这个时候再 &
& 基准和指针 &j &所指向元素。
下面给出c++实现代码：
void swap(int &a, int &b)
int split_2(int* a, int low, int high)
int x = a[low];
while (i &= j)
while (a[i] &= x && i&high)
while (a[j] &= x && j&low)
if (i &= j)
swap(a[i], a[j]);
swap(a[low], a[j]);
对这两种划分方法的
：虽然这两种划分的方法不同，但是其目的都是一样的，就是为了确定基准值的最终位置，同时，基准值左边的元素都比基准值小（或者等于）；基准值右边的元素都比基准值大（或者等于）。
4、实现快速排序
基于上面已经给出了快速排序的伪代码，结合划分算法的代码，应该很快就可以写成快速排序的代码。
void quickSort(int *a,int low,int high)
if(low&high)
//选择一种划分算法
int pos = split_1(a,low,high);
//int pos = split_2(a,low,high);
quickSort(a,low,pos-1);
quickSort(a,pos+1,high);
5、算法分析
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。
（1）最坏时间复杂度
&&& 最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，（例如在数组元素已经有序的情况下，）划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
&&& 因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：
&&&&&&&&&&&&&& C
&= n(n-1)/2=O(n
&&& 如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。
（2） 最好时间复杂度
&&& 在最好情况下，每次划分所取的基准都是当前无序区的&
&记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：
&&& 用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn)。
&&& 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n
)，最好时间复杂度为O(nlgn)。
（3）基准关键字的选取
&&& 在当前无序区中选取划分的基准关键字是决定算法性能的关键。
①&三者取中&的规则
&&& &三者取中&规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的Partition算法完全相同。
②取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准
&&& 选取基准最好的方法是用一个随机函数产生一个取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准，这相当于强迫R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。
&&& 随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其它需要数据随机分布的算法。
说明：重新选取好基准后，只需要将基准和第一个元素进行交换处理，这样上面的划分算法代码就可以原封不动啦。
（4）平均时间复杂度
&&& 尽管快速排序的最坏时间为O(n
)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
（5）空间复杂度
&&& 快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。
（6）稳定性
&&& 快速排序是非稳定的，例如[2，
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致快速排序简单应用
编辑：www.fx114.net
本篇文章主要介绍了"快速排序简单应用"，主要涉及到快速排序简单应用方面的内容，对于快速排序简单应用感兴趣的同学可以参考一下。
一 快速排序基本思想步骤：在实际应用中，要 用到递归，反复进行分割，分割后又快速排序。
1.在表第一个、中间一个与最后一个元素中取中间值项，设为P（k），并将P(k)赋予T,再将表的第一个元素移动P（k)的位置；
2.然后设指针i，j分别指向表的起始和最后位置。
3.反复做以下两步：(1)将 j 逐渐减小，并逐次比较P（j）与T，直到发现P（j）&T为止，将p(j)移到p(i)的位置上；
&&&&&&&&&&&&&&&&&&&&&&&&&&&& （2）将 i 逐渐增加，并逐次比较P（i）与T，直到发现P（i)&T为止，将p(i)移到p(j)的位置上。
4.上述交替进行，直到指针i和j指在同一位置（i=j）为止，此时再将T移到P(i)位置。
二 快速排序C++表示：
#include &iostream&
#include &bubSort.h&
//冒泡排序
template &class T&
void qck(T p[],int n)
//子表长度大于10，用快速排序
i=split(p,n);
//对表进行分割
//对前面的表进行快速排序
s=p+(i+1);
m=n-(i+1);
//对后面的表进行快速排序
bubsort(p,n);
//子表长度小于10，用冒泡排序
template &class T&
static int split(T p[],int n)
int i,j,k,l;
i=0;j=n-1;
k=(i+j)/2;
if((p[i]&=p[j])&&(p[j]&=p[k])) l=j; //从第一个值，中间值，最后值，中选取中间值作为标记
else if((p[i]&=p[k])&&(p[k]&=p[j])) l=k;
//选取一个元素为T
p[l]=p[i];
while(i!=j)
while((i&j)&&(p[j]&=t)) //逐渐减小j，直到发现p[j]&t
p[i]=p[j];i=i+1;
while((i&j)&&(p[i]&=t))
//逐渐增大i，直到发现p[i]&t
p[j]=p[i];j=j-1;
return(i);//返回分界线位置
三 具体应用实例：
#include &qck.h&
#include &iomanip&
#include &ctime&
int main()
/* double p[50],r=1.0;*/
int p[50];
for(i=0;i&50;i++)
//产生50个0~1之间的随机数
r=2053.0*r+13849.0;j=r/65536.0;
r=r-j*65536.0;p[i]=r/65536.0;
for(i=0;i&50;i++)
//产生50个100~300之间的随机数
p[i]=100.0+200.0*p[i];
srand(time(0));
for(i=0;i&50;i++)
p[i]=rand()%500;
cout&&&排序前的序列：&&&
for(i=0;i&10;i++)
for(j=0;j&5;j++)
cout&&setw(10)&&p[5*i+j];
qck(p,50);
cout&&&排序后的序列：&&&
for(i=0;i&10;i++)
for(j=0;j&5;j++)
cout&&setw(10)&&p[5*i+j];
四 实验结果：
#include &qck.h&
#include &iomanip&
#include &ctime&
int main()
/* double p[50],r=1.0;*/
int p[50];
for(i=0;i&50;i++)
//产生50个0~1之间的随机数
r=2053.0*r+13849.0;j=r/65536.0;
r=r-j*65536.0;p[i]=r/65536.0;
for(i=0;i&50;i++)
//产生50个100~300之间的随机数
p[i]=100.0+200.0*p[i];
srand(time(0));
for(i=0;i&50;i++)
p[i]=rand()%500;
cout&&&排序前的序列：&&&
for(i=0;i&10;i++)
for(j=0;j&5;j++)
cout&&setw(10)&&p[5*i+j];
qck(p,50);
cout&&&排序后的序列：&&&
for(i=0;i&10;i++)
for(j=0;j&5;j++)
cout&&setw(10)&&p[5*i+j];
一、不得利用本站危害国家安全、泄露国家秘密，不得侵犯国家社会集体的和公民的合法权益，不得利用本站制作、复制和传播不法有害信息！
二、互相尊重，对自己的言论和行为负责。
本文标题：
本页链接：