共计 1487 个字符，预计需要花费 4 分钟才能阅读完成。
疾速排序与冒泡排序相似，也属于 替换排序 ，通过元素之间的比拟和替换地位实现排序。不同的中央在于，冒泡排序在每一次循环只把一个元素冒泡到数组的一端，而 疾速排序在每一轮筛选一个枢纽元，并让其余比它大的元素挪动到数组的一边，比它小的元素挪动到数组另一边，从而把数组拆分成两个局部。
例如输出如下的数组，枢纽元选取为 6
[8, 1, 4, 9, 0, 3, 5, 2, 7, 6]
宰割之后后果如下
[2, 1, 4, 5, 0, 3, 6, 8, 7, 9]
与归并排序一样，疾速排序也是一种 分治 的递归算法。在分治法的思维下，原数组在每一轮都被拆分成两个局部，每一部分在下一轮又被拆分成两局部，直到不可再分为止。
疾速排序的均匀工夫复杂度是 O(n logn) , 最坏情景的工夫复杂度为 O(n2)，即每一轮循环枢纽元都选到最大或最小的元素，但通过稍许致力能够使这种状况极难呈现。疾速排序有两个外围的问题，枢纽元的抉择 ，以及 元素的替换。
选取枢纽元
枢纽元（pivot），也叫基准元素。在分治过程中，以枢纽元为核心，把其余元素挪动到它的左右两边。选取枢纽元次要有三种办法。
1）选取第一个元素
最简略的办法就是将第一个元素作为枢纽元。然而这种策略不可取，假如输出的数组是预排序的，那么枢纽元必然会选到最大或最小的元素，这种状况下每一轮循环数组并没有被分成两半，不能施展分治法的劣势。在这种极其状况下，疾速排序须要进行 n 轮，工夫复杂度进化为 O(n2)。
2）随机选取元素
一种十分平安的做法是随机选取枢纽元。说这个策略平安，是因为随机的枢纽元不可能在每一轮循环都产生劣质的宰割（即选到了最大或最小值）。然而这个策略也有问题，一是即便是随机选取的枢纽元，也有肯定概率会选中最大或最小值，影响分治效率；二是随机数的生成个别开销很大，影响整体算法效率。
3）三数中值宰割法（Median-of-Three Partitioning）
枢纽元的最好抉择是数组的中值（也叫做中位数，是第 N/2 个最大的数），然而中值难以求出，并且会明显降低疾速排序的效率。个别的做法是应用左端、右端和两头三个元素的中值作为枢纽元。例如输出的数组如下：
[8, 1, 4, 9, 6, 3, 5, 2, 7, 0]
左端元素是 8，右端元素是 0，两头的元素是 6，因而能够确定枢纽元 v = 6。显然，应用三数中值宰割法打消了预排序输出导致的最坏情景。
宰割策略
选取了枢纽元之后，下一步就须要挪动元素，将数组拆分成两个局部。有个简便的办法是间接开三个数组，别离是 smaller，same，larger，而后循环遍历数组的每个元素，将每个元素与枢纽元比照，小于枢纽元的 push 进 smaller 数组，等于枢纽元的 push 进 same 数组，大于枢纽元的 push 进 larger 数组，这样就实现了拆分。然而这样做无疑会占用额定空间，理论的快排（例如 JDK 的 sort 办法）都是间接对原数组进行排序的，这样就要求间接在数组中替换元素，实现数组的宰割。次要有两种办法。
1）双边循环法
首先选定枢纽元 pivot，并且设置两个指针 left 和 right，初始状态下 left 和 right 别离位于数组最左和最右侧。
接下来进行第 1 次循环，从 right 指针开始，让指针所指向的元素和 pivot 进行比拟，如果 大于或等于 pivot，则指针向 左挪动；如果 小于 pivot，则 right 指针进行挪动，切换到 left 指针。轮到 left 指针口头，让指针所指向的元素和 pivot 进行比拟，如果 小于或等于 pivot，则指针向 右挪动；如果 大于 pivot，则 left 进行挪动。
当两个指针都进行挪动时，让 left 和 right 指针所指向的元素进行替换。
而后进行下一轮循环，以此类推。
