更好地理解一种寻找有关它的参考

Question

我试图更好地理解下面显示的算法，而我不成功，由于我不是来自计算机区域。

#include <iostream>
#include <cstdlib>
#include <ctime>
int main() {
  int unsorted[100] = {};
  srand (time(NULL));
  for (int i = 0; i < 100; i++) {
    unsorted[i] = rand() % 100;
  }
  int sorted[100] = {};
  for (int i = 0; i < 100; i++) {
    int hi = -1;
    int hiIndex = -1;
    for (int j = 0; j < 100; j++) {
      if (unsorted[j] > hi) {
        hi = unsorted[j];
        hiIndex = j;
      }
    }
    sorted[i] = hi;
    unsorted[hiIndex] = -1;
  }
}

HIRES提出了一个问题：

• 这种算法是某种经典而已知的算法吗？如果是，它是什么名称，在哪里可以找到有关它的参考。在此参考文献中，如果我能找到有关此算法效率的一些讨论，那就太好了。

• 如果不是经典的算法，我想为理解其逻辑提供一些帮助，并且再次了解效率。

Answer 1

这不是任何经典算法，而是类似于一种算法，通常称为选择。在内部循环的每次迭代的给定代码示例中，我们在未分组数组中查找最高数字，并将其放入排序的数组中的ITH索引中，然后将此数字-1在未分类的数组中制成。例如，考虑给定的数组

未分类：5、7、2、9、6排序阵列：

第一次迭代外循环：i = 0，hi = 9，hiindex = 3

未分类：5，7，2，-1，6排序：9

在外循环的第二次迭代之后：i = 1，hi = 7，hiindex = 1

未分类：5，-1，2，-1，6排序：9，7

您会看到Wee继续前进，我们的列表以降序排序中的降序排序。

该算法的时间复杂性为O(n^2(，这不是分类数组的非常有效的方法。如果我们在数组中有负数，则该算法将失败，例如，以上算法无法对此列表进行排序{1,5，-5,7，-9] AS -1大于-5和-9

Answer 2

这似乎是一种相当简单但效率低下的算法，可以多次通过输入数组，并将其发现的最高数字移至另一个数组中。如果您正在寻找一种分类算法，那将非常效率低下，并且使用额外的空间。您可能想研究更有效的东西，例如快速排序或合并排序。

Answer 3

排序算法与选择排序非常相似。它具有O(n²(的(相当糟糕的(运行时。

但是，此实现甚至比"正常"的实现还要糟糕，因为它与两个数组一起使用：原始一个和排序的数组。通常，选择排序将进行在场(只有一个数组(。这有一个好处，即内部循环可以跳过已经分类的数组元素。

此实现的另一个缺点是它不适合负数。但是也许这里不是必需的。