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：真的吗？