快速排序作为编程方法

1960年，K. A.灰白开发了一种信息的快速分拣，成为最有名的。 如今，它被广泛用于编程，因为它有很多积极的特性：它可以用于一般情况下，它需要额外的内存小的增加，不同类型的列表的兼容，易于实现。 但也有缺点，它具有快速排序：使用工作允许犯了很多错误，这是有些不稳定。

但是，它是研究最多的版本。 首付款，霍尔之后，很多做了密集的研究。 大基地成立于寻找花在工作，这是由经验证据支撑了时间的理论问题。 有改善的基本算法，提高速度实际的建议。

快速排序是很常见的，它到处都可以找到。 在其基础上的方法被实现TList.Sort，存在于（除1）的Delphi，时间的库函数花费来完成，在的qsort C ++所有版本。

操作的基本原则，可以配制成“分而治之”。 它发生断裂列表分为两组，并进行排序通过自身各部分。 由此可见，更应注意的分离过程，在此期间，将发生以下情况：由基础元件确定，并且已重新排列相对他的整个列表。 建一组候选的左侧时，它的值小于所有其他传输规则。 事实证明，在排序列表中的主要元素是其应有的地位。 下一阶段 - 用于相对于所述基座元件的两侧上的挑战递归排序功能。 它结束的过程只能如果列表中只包含一个元素，即进行排序。 因此，为了掌握编程函数作为快速排序，有必要知道的较低级别的算法的工作：a）所述基体部件的选择; b）中的最有效的排列的列表，以产生两套具有更小和更大的值。

与第一原则熟悉。 当选择基础构件，最好应该从平均列表中选择。 然后对折被分成相等的两半。 只要计算出 平均值， 在列表中是非常困难的，所以即使是最快的排序绕过这个演算的一面。 但随着最大或最小值基本元素的选择 - 也不会是最好的选择。 在情况下，一个的这样的确定产生空列表将得到保证，并且第二满。 因此，作为基底构件应选择一个更接近平均值，但对最大和最小的结论。

一旦选择确定，您可以继续分解算法。 这种所谓的内环快速排序。 一切都建立在两个快速访问索引：先经过由左到右，第二，相反的元素，从右到左。 开始操作执行正确的：指数是名单上所有的值进行比较为主。 循环结束时该元素是小于或等于基准。 也就是说，有一个比较和降低指数的值。 在左侧，当工作完成后，大于或等于价值。 在这里，比较值的增加。

在这个阶段，分割算法，其包括快速排序的，两种情况可能发生。 第一个是左边的指数小于右边。 这表明一个错误，再就是它在列表中规定的元素在错误的顺序。 输出 - 改变自己的地方。 第二种情况是当两个柱的是等于或交叉。 这表明该列表的成功分离，也就是说，工作现在已经完成。