这是什么类型的排序？
我正在阅读的 C++ 书籍描述了一种排序算法，说它是冒泡排序，但我找不到像它一样的冒泡排序的单一变体。我知道差异很小，但它是否与常规冒泡排序一样有效？
BubbleSort(int A[], int length)
for (j=0; j < length-1; j++)
for (i=j+1; i < length; i++)
if (A[i] < A[j])
Swap()
基本上，它不是比较两个相邻的值，而是将第一个 A[0] 与每个条目进行比较，在下一次传递时，它将 A[1] 与其余条目进行比较，然后是 A[2] 等。
这真的只是常规的冒泡排序吗，特性和性能是否完全一样？
The C++ book I'm reading described a sort algo, saying it is the Bubblesort yet I cannot find a single variation of bubblesort just like it. I understand the differences are minor, but is it exactly as efficient as a regular bubblesort ?
BubbleSort(int A[], int length)
for (j=0; j < length-1; j++)
for (i=j+1; i < length; i++)
if (A[i] < A[j])
Swap()
Basically, instead of comparing two adjacent values, it compares the first A[0] with every entry, on the next pass it compares A[1] with the remaining entries, then A[2] etc.
Is it really just a regular bubblesort, is the characteristics and performance exactly the same?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这是选择排序。在每次遍历中，您都会找到第 i 个最小元素并将其放在位置 i 上。第一遍之后就不用再看A[0]了，以此类推。选择排序的最坏情况为 O(n2)，最好情况为 O(n)，就像冒泡排序一样，但它的常数因子比冒泡排序更小。 插入排序，一种额外的改进，甚至更好，比大多数 O( n log n) 非常小的数组（少于十个元素左右）的算法，因此严肃的库排序原语将针对小子问题切换到它。
This is selection sort. On each pass you find the i'th smallest element and put it in position i. After the first pass, it is not necessary to look at A[0] anymore, and so on. Selection sort is worst-case O(n2) and best-case O(n), just like bubble sort, but it has a smaller constant factor than bubble sort. Insertion sort, an additional refinement, is even better, to the point where it's faster than most O(n log n) algorithms for very small arrays (fewer than ten elements or so) and so serious library sort primitives will cut over to it for small subproblems.
这种排序类似于选择排序，因为每次通过外部循环都会识别出最佳元素并将其从进一步的考虑中删除。然而，在传统的选择排序中，最好的元素与要删除的元素交换，而其他元素则保持不变。在您列出的排序中（在“基本方法到基本”等地方找到，IIRC），其他一些元素也会被交换。我不认为额外的交换完成任何特别有用的事情，并且排序失去了冒泡排序的唯一优势（适合在纯顺序访问媒体上实现）
This sort is similar to selection sort, in that each pass through the outer loop identifies the best element and removes it from further consideration. In a traditional selection sort, however, the best element is swapped with the element to be removed and other elements are left alone. In the sort you list (found, IIRC, in "A Basic Approach to Basic" among other places) some other elements will get swapped around as well. I don't think the extra swaps accomplish anything particularly useful, and the sort loses out on just about the only advantage bubble sort has (suitability for implementation on purely-sequential-access media)
对我来说，该算法看起来更像插入排序，因为它们共享相同的（外部）循环不变式 - 在外部循环的第 j 个迭代之后，第 j 个最小元素处于正确的位置。
另一方面，冒泡排序的特征是它总是交换相邻元素（您的代码片段中不满足该属性）。
该算法的时间复杂度为
O(n^2)，就像冒泡排序和插入排序（以及最坏情况下的快速排序）一样。The algorithm looks more like insert sort to me, as they share the same (outer) loop invariant -- after
j-th iteration of the outer loop, thejsmallest elements are in their correct positions.On the other hand, the characteristic property of bubble sort is that it always swaps neighboring elements (a property which is not satisfied in your snippet).
The time complexity of this algorithm is
O(n^2), just like bubble sort and insert sort (and quick sort in the worst case).对我来说，它看起来像是选择排序。该算法的工作原理如下（如 wiki 页面上所述）：
It looks like a Selection Sort to me. The algorithm works as follows (as described on the wiki page):