这里用的是哪种排序算法

Question

在在线活动中，我必须完成部分完成的代码。它们使用链表数据结构来存储每个元素。时间复杂度为O(n*n)在外部(for)循环中，当node->next!= NULL(即只检查n-1次)。内部(for)循环，有n次检查，直到(ptr变为NULL)

假设有5个元素。而且,给定顺序的元素5 ->3 ->1 ->2 ->4 ->NULL

周期:

1 ->3 ->5 ->2 ->4 ->NULL

1 ->2 ->5 ->3 ->4 ->NULL

1 ->2 ->3 ->5 ->4 ->NULL

1 ->2 ->3 ->4 ->5 ->NULL

元素排序

1 ->2 ->3 ->4 ->5 ->NULL

这里使用的是哪种排序算法?

Answer 1

这是一个选择排序的实例。注意，在第i次迭代之后，列表的前i个元素现在是有序的，并且移动到第i个位置的元素与原来在那里的元素交换了。例如，下面是第一次迭代到第二次迭代的变化:

5 ->3 ->1 ->2 ->4 ->NULL
1 ->3 ->5 ->2 ->4 ->NULL

注意，1(最小的元素)被交换到前面，但其余元素的顺序相同。类似地，在第二次和第三次迭代之间，您将看到如下内容:

1 ->3 ->5 ->2 ->4 ->NULL
1 ->2 ->5 ->3 ->4 ->NULL

这里，第二小的元素2被交换到第二个位置，但其余元素的顺序相同。

我不知道为什么他们选择在这里使用选择排序。有更好的方法来排序链表。

希望这对你有帮助!

Answer 2

它看起来像选择排序，首先是最小的，然后是最小的，然后把结果放在第一个后面。