1 算法简介
顾名思义，快速排序就是速度非常快的排序算法，快速源于它应用非常精炼和高度优化的内部循环来实现。
2 算法描述
假设对待排序序列进行升序排列，首先随机选取一个元素做为参照值，即枢纽元。然后从右到左选取第一个小于枢纽元的元素a，从左到右选取第一个大于枢纽元的元素b，在保证a的位置在b的位置右侧的情况下，将a与b交换位置，然后继续从b的位置向右，a的位置向左，选取第二对需要交换的元素。需要格外注意的是，打破循环的条件是从左侧序列选取的元素出现在了从右侧选取元素的右侧，即左侧元素位置大于右侧元素位置。这样就以枢纽元为界限，划分为小于枢纽元的小序列和大于枢纽元的大序列，将枢纽元放置于小序列和大序列中间就可以了。之后对分别对小序列和大序列递归上述操作即可。
1> 首先选取44作为枢纽元，从右到左找到第一个小于44的元素33，从左到右找到第一个大于44的元素46,46在33的左侧，将两数交换位置，得到44、33、58、19、25、46序列；然后从46向左找到第一个小于44的元素25，再从33向右找到第一个大于44的元素58,58在25的左侧，交换两数，得到44、33、25、19、58、46序列；然后从右向左找到第一个小于44的元素19，此时左侧序列检测位置与右侧位置重逢，并未达到可交换条件，将枢纽元44与19交换。这样就形成了以44归位后的序列，左侧为全部小于44的元素，后侧为全部大于44的元素。如下图所示：1> 首先选取44作为枢纽元，从右到左找到第一个小于44的元素33，从左到右找到第一个大于44的元素46,46在33的左侧，将两数交换位置，得到44、33、58、19、25、46序列；然后从46向左找到第一个小于44的元素25，再从33向右找到第一个大于44的元素58,58在25的左侧，交换两数，得到44、33、25、19、58、46序列；然后从右向左找到第一个小于44的元素19，此时左侧序列检测位置与右侧位置重逢，并未达到可交换条件，将枢纽元44与19交换。这样就形成了以44归位后的序列，左侧为全部小于44的元素，后侧为全部大于44的元素。如下图所示：
2>采用上述思想，分别对44左侧序列和右侧序列进行排序，最终得到升序序列，如下图所示：
3 算法评价
快速排序的每次交换都是跳跃式的。每次排序的时候设置一个基准点，基准点的选择决定其复杂度的大小，其平均时间复杂度为O(n*logn)，最坏时间复杂度与冒泡算法相同，为O(n^2)。
4 示例程序
5 思考
假如最初给定的序列就是已经排序好的升序序列，每次选取最左侧作为枢纽元时，就出现了快速排序的最差情况，所以选取枢纽元对快速排序的性能有至关重要的决定作用；采用随机选取枢纽元的方法是最安全的；假如每次选取的枢纽元恰好将序列元素平分成两部分，即采用中位数作为枢纽元就达到了最理想的状态。
如果觉得《快速排序算法的点睛分析》对你有帮助，请点赞、收藏，并留下你的观点哦！
