[导读] 前面文章改变世界的5大算法,一文中提到快速排序算法对世界影响巨大,估计很多人不以为然,本文来尝试解读一下为啥。
说到快我只推崇葵花宝典:
皮一下哈,言归正传。
代码如下:
typedef int T_ELEMENT;
int partition(T_ELEMENT A[ ], int left, int right);
/* sort A[left..right] */
void quicksort(T_ELEMENT A[ ], int left, int right)
{
int q;
if( right <= left )
return;
if ( right > left )
{
q = partition(A, left, right);
/* partition分块后 */
//-> A[left..q-1] ≤ A[q] ≤ A[q+1..right]
quicksort(A, left, q-1);
quicksort(A, q+1, right);
}
}
int partition(T_ELEMENT A[], int left, int right);
{
T_ELEMENT P = A[left];
i = left;
j = right + 1;
/*无限循环,使用break退出*/
for(;;)
{
while (A[++i] < P) if (i >= right) break;
/* 此时 A[i] ≥ P */
while (A[--j] > P) if (j <= left) break;
/* 此时 A[j] ≤ P */
if (i >= j ) break; /*退出for循环*/
else swap(A[i], A[j]);
}
if (j == left) return j ;
swap(A[left], A[j]);
return j;
}
举栗子分析:
分成三块了,再递归子块迭代,直到right>left. 这里放一个全过程慢镜头动图,帮助理解:
T(n) = θ(n) + T(i) + T(n-i-1) = cn+ T(i) + T(n-i-1)
其中,i是分区后第一个子块的大小,将T(0)=T(1)= 1作为初始条件。
如果这种情况在每个分区中都重复发生,那么每个递归调用处理一个比前一个列表小1的列表。因此需要在达到大小为1的列表之前进行n - 1次嵌套调用。这意味着调用树是n - 1个嵌套调用的线性链。第i次调用需要做O(n-i)复杂度来进行分区,则
如前所说,如每次执行分区时,都能将列表分成两个几乎相等的两个子块。这意味着每次递归调用都要处理一个只有一半大小的列表。因此,在到达大小为1的列表之前,我们只能进行嵌套调用。这意味着调用树的深度为,但是在调用树的同一级别上没有两个调用处理原始列表的相同部分;因此,每个级别的调用总共只需要O(n)个时间(每个调用都有一些固定的开销,但是由于每个级别上只有O(n)个调用,所以这被包含在O(n)因子中)。结果是,该算法只使用c(n log n)的时间。故时间复杂度为O(n log n)。
要对n个不同元素的数组进行排序,快速排序需要O(n log n)的预期时间,推导很枯燥就不罗嗦了。
图片来自wikipedia:
注:快排不需要额外的缓冲区开销,但是需要栈开销,其空间复杂度为O(log n).
这里对上表其中几个效率相对较高的做个简要介绍,后面如有机会在深入学习总结:
算法应用
说到排序算法复杂度,请一定要与应用场景结合。主要需要考虑待排数据的集的尺寸,如果数据量小的时候放而是插入排序算法应用最为广泛;而对于海量数据场合,则应使用渐近有效排序策略。这是什么意思呢?说白了就是常使用混合算法!主要策略是利用快速排序、堆排序或归并排序将整体快速分治排序,同时对递归底部的小列表采用插入排序。 事实上,在实际应用中有更复杂的变体,例如在Android,Java和Python中使用的Timsort(合并排序,插入排序和其他逻辑),以及在某些C++中用的introsort(快速排序和堆排序) 在.NET中排序实现。
再说白一点,在海量数据场景,利用快速排序、堆排序或归并排序将海量数据快速迭代成收敛的小块,而在小块中采用最为常见的插入排序尽快完成小块排序,小块中采用插入排序则可以更大程度减少递归深度。
在信息时代,有海量信息需要处理,即便有非常强劲的处理器,但如没有很好的算法,仍然无法满足对这些信息的处理。在处理过程中,免不了要进行信息进行排序,快排在时空两个维度的开销都比较均衡,大量的应用软件、开发工具以及软件包都基于快排做了大量的应用。所以说快速排序改变世界,个人认为并不为过。同时对于求职面试,快速排序算法也是高频面试主题,值得深入研究掌握。
本文分享自微信公众号 -嵌入式客栈(embInn),作者:逸珺,严禁商用,违法必究,更多内容请关注
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。