选择排序，插入排序和快速排序的方案 [英] Scenarios for selection sort, insertion sort, and quick sort

问题描述

如果任何人都可以就我的逻辑提供一些意见，我将不胜感激.

If anyone can give some input on my logic, I would very much appreciate it.

对于所有键都相同，选择排序或插入排序的数组，哪种方法运行更快?

Which method runs faster for an array with all keys identical, selection sort or insertion sort?

我认为这与对数组进行排序时类似，这样插入排序将是线性的，而选择排序将是二次的.

I think that this would be similar to when the array is already sorted, so that insertion sort will be linear, and the selection sort quadratic.

哪种方法以相反的顺序，选择排序或插入排序对数组运行更快?

Which method runs faster for an array in reverse order, selection sort or insertion sort?

我认为它们将以类似的方式运行，因为每个位置的值都必须更改.插入排序的最坏情况是反向排序，这意味着它是二次的，然后选择排序也已经是二次的.

I think that they would run similarly, since the values at every position will have to be changed. The worst case scenario for insertion sort is reverse order, so that would mean it is quadratic, and then the selection sort would already be quadratic as well.

假设我们在一个随机排序的数组上使用插入排序，其中元素只有三个值之一.运行时间是线性的，二次的还是介于两者之间?

Suppose that we use insertion sort on a randomly ordered array where elements have only one of three values. Is the running time linear, quadratic, or something in between?

因为它是随机排序的，所以我认为这意味着插入排序所执行的操作数必须比值的数目大很多倍.如果是这种情况，则说明它不是线性的.因此，它可能是二次的，或者可能比二次的要小.

Since it is randomly sorted, I think that would mean that the insertion sort would have to perform many more times the number of operations that the number of values. If that's the case, then its not linear.So, it would likely be quadratic, or perhaps a little below quadratic.

对于长度为N的数组，在Quick.sort()执行期间最大项可以交换的最大次数是什么?

What is the maximum number of times during the execution of Quick.sort() that the largest item can be exchanged, for an array of length N?

最大数量不能超过可用空间的次数，因为它应该一直逼近正确位置.因此，从第一个到最后一个价值点，它将被交换N次.

The maximum number cannot be passed over more times than there are spaces available, since it should always be approaching its right position. So, going from being the first to the last value spot, it would be exchanged N times.

在对所有相等的N个项目进行排序时，quick.sort()会进行多少次比较?

About how many compares will quick.sort() make when sorting an array of N items that are all equal?

绘制快速排序时，可以在每个阶段围绕比较对象绘制一个三角形，即N高和N宽，其面积等于执行比较的次数，即(N ^ 2 )/2

When drawing out the quick sort , a triangle can be drawn around the compared objects at every phase, that is N tall and N wide, the area of this would equal the number of compares performed, which would be (N^2)/2

推荐答案

以下是我对您的评论的评论:

Here are my comments on your comments:

对于所有键都相同，选择排序或插入排序的数组，哪种方法运行更快?

Which method runs faster for an array with all keys identical, selection sort or insertion sort?

我认为这与对数组进行排序时类似，这样插入排序将是线性的，而选择排序将是二次的.

I think that this would be similar to when the array is already sorted, so that insertion sort will be linear, and the selection sort quadratic.

是的，这是正确的.插入排序将为每个元素执行O(1)工作，并访问O(n)元素，从而使整个运行时间为O(n).选择排序总是在时间Θ(n ² )中运行，而不管输入结构如何，因此其运行时间将是二次的.

Yes, that's correct. Insertion sort will do O(1) work per element and visit O(n) elements for a total runtime of O(n). Selection sort always runs in time Θ(n²) regardless of the input structure, so its runtime will be quadratic.

哪种方法以相反的顺序，选择排序或插入排序对数组运行更快?

Which method runs faster for an array in reverse order, selection sort or insertion sort?

我认为它们将以类似的方式运行，因为每个位置的值都必须更改.插入排序的最坏情况是反向排序，这意味着它是二次的，然后选择排序也已经是二次的.

I think that they would run similarly, since the values at every position will have to be changed. The worst case scenario for insertion sort is reverse order, so that would mean it is quadratic, and then the selection sort would already be quadratic as well.

您是对的，这两种算法都具有二次运行时间.该算法实际上应该具有相对可比的性能，因为它们进行的比较总数相同.

You're right that both algorithms have quadratic runtime. The algorithms should actually have relatively comparable performance, since they'll make the same total number of comparisons.

假设我们在一个随机排序的数组上使用插入排序，其中元素只有三个值之一.运行时间是线性的，二次的还是介于两者之间?

Suppose that we use insertion sort on a randomly ordered array where elements have only one of three values. Is the running time linear, quadratic, or something in between?

由于它是随机排序的，所以我认为这意味着插入排序所执行的操作数必须比值的数目大很多倍.如果是这种情况，则说明它不是线性的.因此，它可能是二次的，或者可能比二次的要小.

Since it is randomly sorted, I think that would mean that the insertion sort would have to perform many more times the number of operations that the number of values. If that's the case, then its not linear.So, it would likely be quadratic, or perhaps a little below quadratic.

这应该花费二次时间(时间Θ(n ² )).仅取数组后三分之一中的元素.这些元素中大约有三分之一将为1，并且为了将它们插入已排序的序列中，需要将它们向上移动到数组的2/3以上.因此，完成的工作至少应为(n/3)(2n/3)= 2n ² /9，这是二次方.

This should take quadratic time (time Θ(n²)). Take just the elements in the back third of the array. About a third of these elements will be 1's, and in order to insert them into the sorted sequence they'd need to be moved above 2/3's of the way down the array. Therefore, the work done would be at least (n / 3)(2n / 3) = 2n² / 9, which is quadratic.

对于长度为N的数组，在Quick.sort()执行期间最大项可以交换的最大次数是什么?

What is the maximum number of times during the execution of Quick.sort() that the largest item can be exchanged, for an array of length N?

最大数量不能超过可用空间的次数，因为它应该一直逼近正确位置.因此，从第一个价值点到最后一个价值点，它将被交换N次.

The maximum number cannot be passed over more times than there are spaces available, since it should always be approaching its right position. So, going from being the first to the last value spot, it would be exchanged N times.

这里有一个错误的错误.当数组的大小为1时，最大的元素将无法再移动，因此最大移动数将为N-1.

There's an off-by-one error here. When the array has size 1, the largest element can't be moved any more, so the maximum number of moves would be N - 1.

在对所有相等的N个项目进行排序时，quick.sort()会进行多少次比较?

About how many compares will quick.sort() make when sorting an array of N items that are all equal?

绘制快速排序时，可以在每个阶段围绕比较对象绘制一个三角形，即N高和N宽，其面积等于执行比较的次数，即(N ^ 2 )/2

When drawing out the quick sort , a triangle can be drawn around the compared objects at every phase, that is N tall and N wide, the area of this would equal the number of compares performed, which would be (N^2)/2

这实际上取决于Quick.sort()的实现.具有三元分区的快速排序只能完成O(n)的总工作，因为所有等于枢轴的值都被排除在递归调用中.如果不这样做，那么您的分析将是正确的.

This really depends on the implementation of Quick.sort(). Quicksort with ternary partitioning would only do O(n) total work because all values equal to the pivot are excluded in the recursive calls. If this isn't done, then your analysis would be correct.

希望这会有所帮助！

这篇关于选择排序，插入排序和快速排序的方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！