最佳设想的快速排序的例子（需要有人来检查我的答案是正确的） [英] An example of Best Case Scenario for Quick Sort (Need someone to check if my answer is correct)

问题描述

用的15个数字的列表，我需要给一个列表重新presenting最好的和最坏的情况。它说：QS使用的第一个项目在列表中的支点项目。我不知道如果我每次都挑的第一个项目为支点，但是这就是我假设......

Using a list of 15 numbers, I need to give a list representing the best and worst case scenario. It says "q.s. uses the first item in the list as the pivot item". I'm not sure if I pick the first item as pivot every time, but that's what I'm assuming....

有关最好的情况下..我想出了（黑体为支点，斜体比标记更大和更小的）：

For best case scenario.. I came up with (bold for pivot, italic for bigger and smaller than markers):

8 1 3 2 6 5 7的 4 的 12 的9月11日10 14 13 15

8 1 3 2 6 5 7 4 12 9 11 10 14 13 15

4 1 3的 2 的 6 的5 7--8 - 12 9月11日的 10 的 14 的13 15

4 1 3 2 6 5 7--8--12 9 11 10 14 13 15

2 1 3 的--4 - 6 5 的 7 的。 ....... 8 ........ 10 9 11--12--14 13 15

2 1 3 --4--6 5 7........8........10 9 11--12--14 13 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

希望有人能在这里可以验证我的工作，如果它是错的，指出我如何以及为什么。

Hope someone can here can verify my work and if it's wrong, point out to me how and why.

推荐答案

针对快速排序最好的情况下的条件是，枢轴始终发展顺利，嫌在中间（也许除了在最后阶段），这么多肯定正确。最重要的是你要少掉越好，precise配置为依赖于实施细节。

A condition for the best case for Quicksort is that the pivot always goes right smack in the middle (except perhaps in the very last stages), so much is definitely correct. On top of that you want as few swaps as possible, the precise configurations for that depend on the implementation details.

一个常见的​​实现是第一个交换枢轴进入最后的地方，然后安排其他人，这样的元素小于（或等于）支点来之前更大的元素，最后交换枢纽（从去年的地方）与第一大因素（再复发）。

One common implementation is to first swap the pivot into the last place, then arrange the others so that the elements smaller than (or equal to) the pivot come before the larger elements and finally swap the pivot (from last place) with the first of the larger elements (then recur).

另一种方法是把枢轴到第一时隙安排之前和与最后一个后不超过枢轴交换它

Another method is to put the pivot into the first slot before arranging and swap it with the last not exceeding the pivot after.

有关绝对最好的情况下，这些策略需要不同的配置。例如，

For the absolute best case, these strategies require different configurations. For example,

4 1 3 5 6 7 2

是最好的情况了交换枢纽最后一位变型，而

is a best case scenario for the 'swap pivot into last place' variant, while

4 1 3 2 6 5 7

是一个最好的情况支点原地踏步。

is a best case for 'pivot stays put'.

的最糟糕的情况是，当枢轴总是转到阵列的端部之一，precise细节再次取决于实施，但排序或反向排序通常最坏的情况

The worst case scenario is when the pivot always goes to one of the ends of the array, precise details again depend on the implementation, but sorted or reverse sorted are usually worst cases.

这篇关于最佳设想的快速排序的例子（需要有人来检查我的答案是正确的）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！