快速排序基本原理（快速排序原理）

大家好,小东方来为大家解答以上的问题。快速排序基本原理，快速排序原理这个很多人还不知道,现在让我们一起来看看吧！

1、先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束。

2、 在当前无序区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]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止 快速排序的基本思想是基于分治策略的。

3、对于输入的子序列L[p..r]，如果规模足够小则直接进行排序(比如用前述的冒泡、选择、插入排序均可)，否则分三步处理: 分解(Divide):将待排序列L[p..r]划分为两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。

4、具体可通过这样的途径实现:在序列L[p..r]中选择数据元素L[q]，经比较和移动后，L[q]将处于L[p..r]中间的适当位置，使得数据元素L[q]的值小于L[q+1..r]中任一元素的值。

5、 递归求解(Conquer):通过递归调用快速排序算法，分别对L[p..q]和L[q+1..r]进行排序。

6、 合并(Merge):由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序，即自然合并。

7、 这个解决流程是符合分治法的基本步骤的。

8、因此，快速排序法是分治法的经典应用实例之一。

本文到此分享完毕，希望对大家有所帮助。

免责声明：本文由用户上传，如有侵权请联系删除！