algorithm - 这里使用了哪种排序算法

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

这是 selection sort 的一个实例.请注意，在迭代 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 被交换到第二个位置，但其余元素的顺序相同。

我不确定他们为什么选择在这里使用选择排序。有 much better ways to sort a linked list .

希望这对您有所帮助!