c++ - 如何对链表执行选择排序？

Question

我正在尝试在链表上实现选择排序。我希望它直接在链表上执行，而不是复制，使用节点指针而不是我在这里粘贴的数组索引方法:

void listClass::selectionsort(int array[], int size)
{
    int startscan, minIndex, minValue;

for (startscan = 0; startscan < (size - 1); startscan++) 
{
    minIndex = startscan;
    minValue = array[startscan];
    for (int index = startscan + 1; index < size; index++) 
    {
        if (array[index] < minValue)
        {
            minValue = array[index];
            minIndex = index;
        }
    }
    array[minIndex] = array[startscan];
    array[startscan] = minValue;
}
}

如何调整此函数以接受我的链表？并排序？我也不想使用任何类型的 STL 容器。

Answer 1

假设列表是 { 90, 13, 5, 12 }。在开头开始一个指针。

{ * 90、13、5、12

在指针之后找到最小的成员并将其移动到指针之前。

{ 5, * 90, 13, 12 }

在指针之后找到最小的成员并将其移动到指针之前。

{ 5, 12, * 90, 13 }

再次。

{ 5, 12, 13, * 90 }

再次。

{ 5, 12, 13, 90 }

指针跑到列表末尾，我们完成了，列表已排序。