算法图解之快排

发表于 | 分类于 | | 当前热度: ℃
字数统计: 260 | 阅读时长 ≈ 1

D&C算法

在讲快排之前首先需要先介绍一下D&C算法。D&C（divide and conquer），分而治之，一种著名的递归式问题解决方法。下面从几个例子来了解一下：

  1. 假设你是农场主，有一小块（1680m*640m）土地。你要将这块地均匀地分成方块，且分出的方块要尽可能大。如何将一块地均匀地分成方块，并确保分出的方块是最大的呢？使用D&C策略！D&C算法是递归的。使用D&C解决问题的过程包括两个步骤：
    （1）找出基线条件，这种条件必须尽可能简单。
    （2）不断将问题分解（或者说缩小规模），直到符合基线条件。

快速排序

快速排序也使用了D&C。它的实现原理：以一个为基准，将数组分为两部分，再依次将拆分的部分再进行取基准、分组，以此类推。

代码实现

-----------------------本文结束感谢您的阅读-----------------------
坚持原创技术分享，您的支持将鼓励我继续创作！
0%