>> MARK GROZEN-史密斯：嗨，我是马克 Grozen史密斯，这是快速排序。
就像插入排序和冒泡 排序，快速排序是一种算法
排序的列表或一个事物的数组。
为简单起见，我们假设这些 事情是整数，但
知道快速排序的工作 不仅仅是数量多。
快速入门是比较复杂一点 比插入或泡沫，但它的
还更高效 在大多数情况下。
等待第二个。
难道他只是说“最 例“，而不是”所有“？
有趣的是，没有。
不是所有的情况下都是相同的。
不要担心这个细节，如果你 没见过大O表示法还，但
快速排序是一种O（n平方）算法 在最坏的情况，就像
插入或冒泡排序。
然而，它典型地充当多 像一个旧的模拟米的算法。
为什么呢？
我们会尽快给后来。
但是现在，就让我们学习 快速排序是如何工作的。
>> 因此，让我们走过Quicksorting这 从最小的整数数组
到最大。
在这里，我们有6个整数， 5，1，3，8,4，7,9，和2。
首先，我们选择的最后一个元素 这个数组 - 在这种情况下，2 -
并调用了“支点”。接下来，我们 开始看两件事情 -
1，最低的指数，我将把 为留到右侧
壁，并且，两个，最左边的 要素，我称之为“当前
元素。“我们现在要做的是 看看所有其他元素，其他
比支点，并把所有的元素 比枢轴到较小
左墙和所有 比枢轴到较大
右墙。
然后，终于，我们将删除该支点 右边上墙把它之间
所有比它更小的数字 和所有较大的数字。
>> 因此，让我们做到这一点。
拿起2，把墙上的 开始，并调用6“当前
元素“，所以我们想看看 我们目前的元素时，6。
而且，由于它比大 2，我们将它留在了
右墙。
然后，我们继续来看看5作为我们 当前元素，看到这
是，再次，比枢轴较大，所以我们 离开它的地方是在右边
壁的一侧。
我们继续前进。
我们目前的元素是 现在1和 - 哦。
现在，这是不同的。
当前元素现在比小 枢轴，所以我们要把它
向壁的左边。
要做到这一点，让我们切换 当前元素具有最低索引
坐在刚刚在墙上的权利。
现在，我们将墙上了一个索引 因此，图1是在左边
现在壁的一侧。
>> 等待。
我只是混在的元素 右侧墙上的，不是吗？
不要担心。
这很好。
我们关心现在唯一 是，所有这些元素的
右墙的块头大 比支点。
没有实际的顺序是假设呢。
>> 现在，回到分拣。
因此，我们继续看 元件的其余部分。
在这种情况下，我们可以看到，有 不及的其他元素
支点，所以我们把它们全部在 右侧壁。
最后，我们得到当前元素 并认为它是支点。
现在，这意味着，我们有两个 数组，第一个是各款
小在枢轴和左侧 壁，所述第二感的
比枢轴到较大 右侧的墙上。
我们希望把之间的支点元素 二，然后我们就会知道
该枢轴是在其右 最终排序的地方。
所以我们打开了第一个元素 右侧壁与枢转的，
我们知道枢轴的 在它的右侧位置。
>> 然后，我们重复这个过程为 子阵列左和枢轴的权利。
自上次子阵列中只有一个 元长，我们知道这已经
排序的，因为你怎么能出 命令，如果你只有一个元素？
对于右侧的子阵列，我们 看，所述枢轴是5，和壁
是刚刚离开的6。
以及当前元素也 开始时为6。
所以图6是大于5。
我们离开它的地方是在 右侧的墙上。
现在，移动上，3小于5。
因此，我们的第一个元素打开它 恰到好处的墙。
现在，我感动了堵墙之一。
现在，移动到8。
图8是大于5时， 所以我们离开它。
4小于5，因此，我们切换它。
而上。
>> 我们每次重复这个过程就 阵列的左侧和右侧。我们
选择一个支点，做的比较 和创建的另一个水平向左和
右子数组。
这个递归调用将持续到 我们到达的时候，我们已经结束
瓜分了整个阵列成 刚子数组长度为1的。
从那里，我们知道数组进行排序 因为每一个元素都有，在
某一点上，一直是一个枢轴。
换句话说，对于每个元素，所有 该数字的左侧有一个更小
价值观和所有的数字到 右有更大的价值。
>> 此方法效果非常好，如果在 选择枢轴的值是
约在中间 范围列表的值。
这意味着，当我们移动 周围的元素，大约有尽可能多的
元素，以枢轴的左 因为有在右边。
和的分而治之的性质 快速排序算法，然后采取
充分利用。
这将创建为O运行时（n日志N，） 第n因为我们必须做N减1
在每一代和日志比较 N，因为我们必须将列表
记录n次。
然而，在最坏的情况下，这 算法其实是可以为O（n
平方。）假设在每一代中， 枢轴只是恰巧是
最小或最大的 我们正在整理的数字。
这将意味着打破列表 n次且用N减1
比较每一次。
因此，O n个平方。
>> 我们如何能改善的方法？
改善方法的一个好方法是 切下来的概率
运行时是有史以来实际上 二六，O n的平方。
记住这个最坏的情况，最坏的情况下 只能发生在
支点选择始终是最高的 或阵列中的最低值。
以确保这是不太可能发生， 我们可以通过找到支点
选择多个元素和 取中间值。
>> 我的名字叫马克Grozen-史密斯， 这是CS50。
>> 为简单起见，我们假设这些 事情是整数，但
知道Quicksert -
Quicksert？
抱歉。
>> 在这里，我们有整数 6，5,1，3,8，4,9。
>> 扬声器1：真的吗？
>> 扬声器2：不要停​​在那里。
>> 扬声器1：真的吗？