快速排序算法学习

数据结构与算法之快速排序学习

　　这段时间一直在看关于python的知识，偶然翻到python的算法讲解中关于快速排序的例子，与是兴趣大气，在此写下一些自己的心得体会。
　　快速排序是所有的已知排序的算法中最快的算法，但是在实践中人们却很难写出正确的快速排序的代码。它与归并排序一样属于一种分治递归的算法。假设有数组s，快速排序的步骤可简单总结如下：
　　1， 如果数组的元素是0或者1个则返回（后面枢纽元的选取采用三数中值分割法，这个情况另当别论后面讨论）
　　2，取s的元素v最为枢纽元（这个的选取很重要）
　　3，将s-{v}(s中其余的元素）分成两个不相交的集合：s1={x∈s-{v}|x<=v},s2={x∈s-{v}|x>=v}.
　　4，对两个子序列再执行上述三个步骤
　　快速排序在平均的时间复杂度O(nlogn)，在最坏的情况下时间复杂度是O(n^2)。下面重点讲一下关于枢纽元的选取
一种错误的做法：
　　现在网上流程的教程好多都是直接选用数组的第一个元素作为枢纽元进行排序。殊不知这种情况在很多情况是会导致最坏的事件复杂度的发生。比如数组在为非递减数组的情况下，事件复杂度会直接上升到Ｏ(n^2)，强烈建议不要采用这中策略
一种安全的做法：
　　一种安全的做法是随机选取枢纽元，一般来说这种策略非常安全，但是由于使用随机数生成器代价很昂贵，算法的时间复杂度并不会显著的降低，这种也不推荐
三数中值分割法：
　　在实际的项目开发中我们经常采用这种策略，在具体的应用中稍微变一个形。通常使用数组左端，右端和数组中间的三个数。把最大的数放在数组的最右端，最小的放在数组的最左端，剩下的放在数组的中间。我们的枢纽元就是采用中间的那个数。下面用一个实际的例子来说明一下这个情况，这个例子来自《数据结构与算法》洋人的那本，不严蔚敏写的那本看看入门还可以，别的不做评价。

　　这里首先得到了数据的中值，然后把中值放在了数组的倒数第二位，这样做的好处是可以解决令人很崩溃的停止问题。对这个问题的描述我们还是直接上代码解决分析
　　
　　这是快速排序的主体程序，三元素中的最大者放到了Ａ[right],因为它大约枢纽元我们可以把枢纽元放到Ａ[right-1]并在分割阶段将ｉ和ｊ初始化到left+1和right－２。因为Ａ[left]比枢纽元小，所以将它用到ｊ的警戒标记。不必担心ｊ会越界。由于ｉ将停在那些等于枢纽元的关键字处，故将枢纽元存储在Ａ[right-1]，将提供一个警戒标记。我们不必担心。此处有个小问题当元素个数小于3个时建议使用别的排序方法直接排序，然后返回，此处偷懒。在数据重复很多时会出现bug