这里使用哪种排序算法

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,第二个最小元素,交换到第二个位置,但其余元素的顺序相同.

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

希望这可以帮助!