如何在链表上执行选择排序

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}

指针指向列表的末端，我们完成了，列表被排序了

Answer 2

这是不使用STL的链表选择排序的c++实现。为了方便不同情况下的程序测试，这个程序创建了一个给定大小的随机数字链表。

    //Program to sort a linked list using selection sort.
    #include<stdio.h> 
    #include<time.h>
    #include<cstdlib>
    #define size 10 //Size of linked list.
    struct node
    {
         int info;
         struct node *next;
    }*start=NULL;
    typedef struct node * Node;
    int main()
    {
         int i;
         Node ptr;
         void selectionsort(Node);
         srand(time(NULL));
         for(i=0;i<size;i++)
         {
              Node ptr,temp;
              ptr=(Node)malloc(sizeof(node));
              ptr->info=rand()%100; //Random linked list of given size is created.
              ptr->next=NULL;
              if(start==NULL)
              {
                   start=ptr;
              }
              else
             {     temp=start;
                   while(temp->next!=NULL)
                         temp=temp->next;
                   temp->next=ptr;
             }          
         }
         printf(" Linked List Before Sorting Is -n");
         ptr=start;
         while(ptr!=NULL)
         {
              printf(" %d ",ptr->info);
              ptr=ptr->next;
         }
         printf("n Linked List After Sorting Is -n");
         selectionsort(start);
         ptr=start;
         while(ptr!=NULL)
         {
              printf(" %d ",ptr->info);
              ptr=ptr->next;
         }
         return 0;
    }
    void selectionsort(Node start)
    {
             Node ptr=start,temp,address;
             int var;
             while(ptr->next!=NULL)
             {
                 temp=ptr;
                 address=temp;
                  while(temp!=NULL)
                  {
                        if((address->info)>(temp->info))
                        address=temp;
                        temp=temp->next;
                  }
                  var=address->info;
                  address->info=ptr->info;
                  ptr->info=var;
                  ptr=ptr->next;
            }
    }

详细信息请访问-https://github.com/SahdevKansal02/Data-Structures-And-Algorithms.git