一、快速排序原理

快速排序是一种基于分治思想的排序算法。在快排中,我们的工作主要集中在划分而不是合并子问题。

首先我们要选择一个中轴,把比中轴大的元素放在它的右边,比他小的放在它的左边。中轴的选择有很多种,其中最简单的就是把第一个元素当作中轴。

二、从两端同时扫描交换

    首先选择子数组的第一个元素为中轴,即P = A[s]。分别从子数组的两端进行扫描,并且将扫描到的元素与中轴进行比较。
从左到右的扫描(下面用指针i表示)从第二个元素开始。扫描忽略小于中轴的元素,直到遇到第一个大于等于中轴的元素(注释1)为止。从右到左的扫描(下面用指针j
表示)从最后一个元素开始。扫描忽略大于中轴的元素,直到遇到第一个小于等于中轴的元素为止。

当两端的扫描全部终止之后,会发生3种情况:



i与j不相交

      这时意味着i<j,只要简单的交换A[i]与A[j]的值,再分别对i+1,j-1,然后继续开始扫描。

i与j相交

      i与j相交,也就是i > j。把A[s](中轴)和A[j]交换后我们就完成了对该数组的一次划分。此时j左面元素小于A[j],右边元素大于A[j]。

i与j相等

      如果扫描终止之后两个指针指向同一个元素,也就是i=j,被指向的元素的值一定等于p(注释2)。此时j
左面元素小于A[j],右边元素大于A[j]。我们得到了数组的一次划分。

我们可以把第二种和第三种情况合起来,只要i>=j,就交换中轴和A[j]的位置。

伪代码:

            //以第一个元素为中轴,对子数组进行划分


            //输入:数组A[0..n-1]中的子数组A[s...e],由左右下标s和e定义


            //输出:A[s...e]的一个划分,分裂点的位置作为函数的返回值


               p <- A[s]


                i <- s; j <- e+1


                repeat


                        repeat   i <- i+1 until A[i] >= p

                        repeat   j <- i-1 until A[j] <= p


                        swap(A[i], A[j])


                until   i >= j


                swap(A[i], A[j])//当i>=j时撤销最后一次交换


                swap(A[s],A[j])


                return   j


参考代码如下:
#include<iostream> using namespace std; void swap(int &a,int &b){ int temp;
temp = a; a = b; b = temp; } void qsort(int a[],int s,int e){ if(s >= e)
return; int p = a[s]; int i = s+1,j = e; while(true){ while(a[j] > p) j--;
while(a[i] < p && i < e) i++;//注释3 if(i < j) swap(a[i++],a[j--]); else{
swap(a[s],a[j]); break; } } qsort(a,s,j-1); qsort(a,j+1,e); } int main() { int
n; cin >> n; int a[n]; for(int i = 0;i < n;i++) cin >> a[i]; qsort(a,0,n-1);
for(int i = 0;i < n;i++) if(i != n-1) cout << a[i] << " "; else cout << a[i] <<
endl; return 0; }



注释1:为什么遇到与中轴相等的元素也要终止扫描呢?事实上不中止也是可以的,但是当遇到有很多相同元素的数组时,用这个方法可以将数组分的更加平均,从而大大提升算法运行速度。假设有一个长度为n的元素相同的数组,如果遇到等于中轴不中止扫描,那么i会移动到最后一个位置,或者j会移动到第一个位置,那么划分的子数组长度就会分别是n-1
和 1。



注释2:从右向左遍历,当遇到小于或者等于中轴的元素时停止,从左向右遍历,当遇到大于等于中轴的元素时停止。当它们停止时,说明i左侧元素全部小于中轴,j右侧元素全部大于中轴。这样如果i与j停止在同一个元素上,那么说明这个元素小于等于中轴并且大于等于中轴,所以这个元素等于中轴。


注释3:在这种情况下,下标i可能会越过子数组的边界。可以像上面那样每次加1时检查下标越界的可能性,也可以给数组加一个“限位器”,防止它越过n这个位置。但是更巧妙的选择中轴方法可以避免这种情况。

三、一端挖坑,另一端填补



代码如下:

这种写法的主要思想就是从右向左找到第一个小于中轴的数,并与中轴交换,再从左到右找到第一个大于中轴的数,并与中轴交换。这种写法里中轴的位置是不断变化的。
#include<iostream> using namespace std; void swap(int &a,int &b){ int temp;
temp = a; a = b; b = temp; } void qsort(int a[],int s,int e){ if(s >= e)
return; int p = a[s]; int i = s,j = e; while(i != j){ while(j > i && a[j] >= p)
j--; swap(a[i],a[j]); while(i < j && a[i] <= p) i++; swap(a[i],a[j]);
}//处理完后,a[i] = p; qsort(a,s,i-1); qsort(a,i+1,e); } int main() { int a[10] =
{1,8,9,5,4,9,4,56,4,6,}; qsort(a,0,9); for(int i = 0;i < 10;i++) cout << a[i]
<< " "; return 0; }

四、更好的中轴选择方法

更好的中轴选择方法:快排的一个缺陷就是当待排序数组基本有序时,它的复杂度和冒泡排序没什么俩样,甚至更糟,所以就要进行优化。
随机快速排序,它使用随机的元素作为中轴;三平均划分法,它以最左面最右面和最中间元素的中位数作为中轴。相比之下三平均划分法更常用。

三分平均划分法思想本质没变,仅仅只是优化了中轴选择方法而已,注意代码中与上面的不同之处:
#include<iostream> using namespace std; void swap(int &a,int &b){ int temp;
temp = a; a = b; b = temp; } void cmpswap(int &a,int &b){ if(a > b) swap(a,b);
} void qsort(int a[],int s,int e){ if(s >= e) return; int r = s+(e-s)/2;
cmpswap(a[r],a[s]),cmpswap(a[s],a[e]); int p = a[s]; int i = s+1,j = e;
while(true){ while(a[j] > p) j--; while(a[i] < p && i < e) i++; if(i < j)
swap(a[i++],a[j--]); else{ swap(a[s],a[j]); break; } } qsort(a,s,j-1);
qsort(a,j+1,e); } int main() { int n; cin >> n; int a[n]; for(int i = 0;i <
n;i++) cin >> a[i]; qsort(a,0,n-1); for(int i = 0;i < n;i++) if(i != n-1) cout
<< a[i] << " "; else cout << a[i] << endl; return 0; }
首先你可能发现定义了一个新函数,用来交换a、b的值,使a的值总是大于b的值。现在我们的目的是使中轴的元素为最左最右和中间元素中的中位数
,也就是要求a<p<b,其中p为中轴,也就是说我们只要让a[s]的值位于a[r]和a[e]中间就可以了(因为a[s]是中轴),所以我们可以
通过cmpswap()函数来使a[r] < a[s] < a[e] 或者 a[e] < a[s] < a[r]。事实证明这种方法可以大大提高快速排序的适用性。

五、其他的优化


老实说我觉得上面的优化够用了,但是不免有的人会精益求精。事实上快速排序也有很多缺点,比如它对基本有序的数组排序效率极差,但是多年以来人们对这个基本算法进行了坚持不懈的改良,其中有一些重要成果可以了解:



* 随机快速排序
* 三平均划分法
* 当子数组足够小的时候改用插入排序
* 划分方法的改进(三路划分)
三路划分的思想:将数组分成三段,每段的元素数分别小于、等于、大于中轴元素。

六、快速排序的非递归实现(待完成)

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信