快排，保证最坏情况下，栈的深度为log(n)

78 阅读 0 评论 52 点赞

我是靠谱客的博主玩命高山，最近开发中收集的这篇文章主要介绍快排，保证最坏情况下，栈的深度为log(n)，觉得挺不错的，现在分享给大家，希望可以做个参考。

《计算机程序设计艺术》的算法：

1，保持2个指针i,j,开始i=2,j=N

2,如果Ri划分后最终要成为左子文件的一部分（通过比较Ki,Kl知道），i+=1;,

继续进行知道遇到一个属于右子文件的基类Ri为止；

3，类似，j-1知道遇到属于左子文件的记录Rj为止。

4，如果i<j,交换Ri，Rj，然后以同样方式处理下一记录，“两头点蜡”直到i>=j.

5,通过交换Rj，Rl，最终完成划分。

分析：每次划分这个文件，把较长的子文件压入栈，并对另一个较短的子文件进行工作，直到得到容易排序的短文件为止。

可以确保栈绝不包含多于lgN个项目。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。