快速排序的原理是什么

先
数据序列
选
元素,并
序列
所
比该元素
元素都放
右边或左边,再
左右两边
别用同
处
直
每
待处理
序列
度
1,
处理结束
前
序区R[1..H]
任取
数据元素作
比较
"基准"(
妨记
X)
用
基准
前
序区划
左右两
较
序区：R[1..I-1]
R[I+1..H]
且左边
序
区
数据元素均
于等于基准元素
右边
序
区
数据元素均
于等于基准元素
基准X则位于
终排序
位置
即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)
R[1..I-1]
R[I+1..H]均非空
别
进行
述
划
程
直至所
序
区
数据元素均已排序
止
快速排序
基本思想
基于
治策略
于输入
序列L[p..r]
规模足够
则直接进行排序（比
用前述
冒泡、选择、插入排序均
）
否则
三步处理：
解(Divide)：
待排序列L[p..r]划
两
非空
序列L[p..q]
L[q+1..r]
使L[p..q]
任
元素
值
于L[q+1..r]
任
元素
值
具体
通
途径实现：
序列L[p..r]
选择数据元素L[q]
经比较
移
L[q]
处于L[p..r]
间
适
位置
使
数据元素L[q]
值
于L[q+1..r]
任
元素
值
递归求解(Conquer)：通
递归调用快速排序算
别
L[p..q]
L[q+1..r]进行排序
合并(Merge)：由于
解
两
序列
排序
进行
所
L[p..q]
L[q+1..r]都排
序
需要执行任何计算L[p..r]
已排
序
即自
合并
解决流程
符合
治
基本步骤
快速排序
治
经典应用实例

大哥，你也得说怎么排？
大到小？
还是小到大？
还是......
大到小有很多种呢

先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束。
在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止
快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序（比如用前述的冒泡、选择、插入排序均可），否则分三步处理：
分解(Divide)：将待排序列L[p..r]划分为两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。具体可通过这样的途径实现：在序列L[p..r]中选择数据元素L[q]，经比较和移动后，L[q]将处于L[p..r]中间的适当位置，使得数据元素L[q]的值小于L[q+1..r]中任一元素的值。
递归求解(Conquer)：通过递归调用快速排序算法，分别对L[p..q]和L[q+1..r]进行排序。
合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序，即自然合并。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。