c++ - 这是什么类型的？

Question

我正在阅读的 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] 等。

真的只是一个普通的冒泡排序，特性和性能完全一样吗？

Answer 1

这是 selection sort .在每次通过时，您都会找到第 i 个最小的元素并将其放在位置 i。第一遍之后就不用再看A[0]了，以此类推。选择排序是最坏情况下的 O(n²) 和最好情况下的 O(n)，就像冒泡排序一样，但它的常数因子比冒泡排序小。 Insertion sort ，一个额外的改进，甚至更好，它比大多数非常小的数组(少于十个元素左右)的 O(n log n) 算法更快，因此严肃的库排序原语将切换到它来解决小的子问题.