欢迎大家来到IT世界,在知识的湖畔探索吧!
在工作中，如果你的上司让你写一个快速排序，你写不出来，那就不要声张，省的别人取笑你，被称为20世纪十大算法之一的快排算法，应该熟练到手写都能快速完成的地步才算合格，面试的时候面试官也会经常让你手写，作为考察算法的一部分，虽然在我看来手写代码对程序员是一件特别折磨的事，但是很多公司都是这么干的，没办法，要做完全的准备。
《大话数据结构》一书中写到快速排序的基本思想是：通过一趟排序将待排序分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对着两部分记录继续进行排序，以达到整个序列有序的目的。
好 我们来看初级版本的代码：
结果为：
其中：Partition函数要做的就是选取一个关键字，使得左边的值比他小，右边的值比他大，我们将这样的关键字成为枢轴。
在Partition代码里，我们选取枢轴是直接选取的数组的第一个值，想我们举得例子，第一次调用方法只是把9放到了顶端，左边的数字都会比他小，这样整个数列其实没有实质性的变化，也就是说排序的效率很低。
可以这么说快速排序的快慢取决于关键字处在整个数列的位置。（单列一段，很重要）
在现实中，数列极有可能很大一部分是有序的，所以总是固定的选取第一个值就变成了瓶颈，经过小编网上查找找到了一种比较好的选取方法就是三数取中，即去三个关键字先进行排序，将中间的书作为枢轴，一般是取左端，右端和中间三个数。也可以随机选取，这样中间的数接近中间的位置的数的值的概率就大大增加了，所以到来了下一版代码（主要的改进在Partiton函数中对于pivotKey的选取，大家直接看Partition函数的变化即可）：
如果觉得我的文章对你有帮助，请关注我，谢谢，共勉！！！
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://itzsg.com/37285.html
